Hide

Problem C
As Easy as CAB

We all know how to alphabetize a list of distinct words when you know the alphabet: One word may be a prefix of another longer word, in which case the shorter word always comes before the longer word. With any other two words there must be a first place in the words where their letters differ. Then the order of the words is determined by the lexicographical order of these first differing letters.

How about the reverse problem: Can you find the lexicographic order of the alphabet from an ordered list of words? Suppose an alphabet exists where the following list of word strings is given in lexicographical order:

cab
cda
ccc
badca

It is clear that c comes before b in the underlying alphabet because cab comes before badca. Similarly, we know a comes before d, because cab < cda, a comes before c because cab < ccc, and d comes before c because cda < ccc. The only ordering of the 4 alphabet characters that is possible is adcb.

However, it may be that a list contains inconsistencies that make it impossible to be ordered under any proposed alphabet. For example, in the following list it must be that a comes before b in the alphabet since abc < bca, yet it also must be that b comes before a in the alphabet since bca < aca.

abc
bca
cab
aca

Finally, some lists may not provide enough clues to derive a unique alphabet order, such as the following:

dea
cfb

In this list, d comes before c but we don’t know about the relative positions of any of the other letters, so we are unable to uniquely discern the order of the alphabet characters.

Input

The first line of input will contain $L$ and $N$, separated by a space, where $L$ is a lowercase character $\texttt{b} \le L \le \texttt{z}$ representing the highest character in the English alphabet that appears in the derived alphabet, and $N$ is an integer $1 \leq N \leq 1\, 000$ that is equal to the number of strings in the list. Each of the next $N$ lines will contain a single nonempty string of length at most $1\, 000$, consisting only of characters in the derived alphabet. No two strings will be the same.

Output

If the input is consistent with a unique ordering of the alphabet, output a string that designates that ordered alphabet. If the data is inconsistent with any ordering, output IMPOSSIBLE. If the data is consistent with multiple orderings, output AMBIGUOUS.

Sample Input 1 Sample Output 1
d 4
cab
cda
ccc
badca
adcb
Sample Input 2 Sample Output 2
c 4
abc
bca
cab
aca
IMPOSSIBLE
Sample Input 3 Sample Output 3
f 2
dea
cfb
AMBIGUOUS
Sample Input 4 Sample Output 4
e 5
ebbce
dbe
adcd
bc
cd
edabc

Please log in to submit a solution to this problem

Log in