시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 1024 MB | 23 | 13 | 10 | 55.556% |
You are on vacation in a foreign country. This country has a local football league, and you don't know any of the team names. However, you have found a table of all the results from this season, and next to every match is the concatenated names of the two teams that played.
There are $n$ teams in total, named $s_1, s_2, \cdots, s_n$. You are given the concatenation $s_i+s_j$ for every ordered pair $i \neq j$. Find the teams names $s_1, s_2, \cdots, s_n$. Team names must be nonempty, but they do not need to be distinct.
The first line of input contains the integer $n$ ($2 \leq n \leq 500$).
The following $n$ lines each contain $n$ strings, the table of concatenated team names. The $j$:th string on the $i$:th of these lines will contain the string $s_i + s_j$ if $i \neq j$, and "*" if $i = j$. The concatenated team names will consist of lower case characters a-z.
The total number of characters in concatenated team names is at most $10^6$.
If there is no solution, print "NONE".
If there is more than one solution, print "MANY".
If there is one unique solution, print "UNIQUE", followed by $n$ lines containing $s_1, s_2, \cdots, s_n$.
3 * difaik difhammarby aikdif * aikhammarby hammarbydif hammarbyaik *
UNIQUE dif aik hammarby
2 * aaaa aaaa *
MANY
3 * a ab a * b ba b *
NONE
2 * zz zz *
UNIQUE z z
ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2022 F번