Foreign Football

시간 제한5초메모리 제한1024 MB

요약

모든 순서쌍에 대한 s_i+s_j 연결 문자열이 주어질 때, n개의 비어 있지 않은 이름을 복원하거나 해가 없거나 여러 개임을 판정한다.

난이도: 보통10점 중 6점
유형: 문자열, 문자열 매칭, 구현
정답자: 아직 제출이 없습니다

문제

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$ .

예제4

예제 1

입력

3
* difaik difhammarby
aikdif * aikhammarby
hammarbydif hammarbyaik *

예상 출력

UNIQUE
dif
aik
hammarby

예제 2
입력
```
2
* aaaa
aaaa *
```
예상 출력
```
MANY
```
예제 3
입력
```
3
* a ab
a * b
ba b *
```
예상 출력
```
NONE
```
예제 4
입력
```
2
* zz
zz *
```
예상 출력
```
UNIQUE
z
z
```