Hide

Problem F
Foreign Football

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 s1,s2,,sn. You are given the concatenation si+sj for every ordered pair ij. Find the teams names s1,s2,,sn. Team names must be nonempty, but they do not need to be distinct.

Input

The first line of input contains the integer n (2n500).

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 si+sj if ij, 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 106.

Output

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 s1,s2,,sn.

Sample Input 1 Sample Output 1
3
* difaik difhammarby
aikdif * aikhammarby
hammarbydif hammarbyaik *
UNIQUE
dif
aik
hammarby
Sample Input 2 Sample Output 2
2
* aaaa
aaaa *
MANY
Sample Input 3 Sample Output 3
3
* a ab
a * b
ba b *
NONE
Sample Input 4 Sample Output 4
2
* zz
zz *
UNIQUE
z
z
Hide

Please log in to submit a solution to this problem

Log in