By Pablo A. Heiber, Universidad Nacional de La Plata Argentina
The International Committee for Professional Chess (ICPC) organizes a Tournament for Advanced Players (TAP) with a very strange methodology. As expected, in each game exactly two players face each other, but in this case only one game takes place at a time, because there is only one chess board available. After receiving the inscriptions for the competitors and assigning them a number, the organization decides arbitrarily what matches are going to take place, and in which order. Each competitor can face any other competitor any number of times, and it is even possible that some competitors never play against others. Once built the general fixture of all the matches to be played, the organization hands each competitor a non-empty list of their rivals, in chronological order (that is, the order in which the matches will take place).
Florencia signed up in first place, so that she was assigned the number 1. After chatting a bit with the other competitors, she realized that she had lost her list of rivals. Because she does not want to bother the TAP's organizers, she has asked all the other competitors for a copy of their own lists of rivals, hoping that with this information she would be able to reconstruct her lost list. Florencia is not sure if there exists a unique general fixture that is compatible with all the copied lists that she was given by the other competitors. However, she knows that the list that she was given by TAP's organizers is in fact unique. Your task is to help her reconstruct this list.
Each test case is described using two lines. The first line contains a single integer number N, representing the number of competitors (2 ≤ N ≤ 9). Each competitor is identified by a different integer from 1 to N, and competitor number 1 is always Florencia. The second line contains N-1 non-empty strings Li of at most100 characters each (for ;i = 2, 3, ..., N). The string Li is composed solely of digits between 1 and N, excluding digit i, and represents the list of rivals of competitor number i in chronological order. Note that competitor number 1 appears at least once in one of the given lists. In each test case, there exists a unique list of rivals for competitor number 1 that is compatible with the other lists of rivals. The end of the input is signalled by a line containing the number -1.
For each test case, you should print a single line containing a string, representing the unique list of rivals of competitor number 1 (Florencia) that is compatible with the lists of rivals of the other competitors. The rivals indicated in this list must appear in chronological order.
|Input Sample||Output Sample|
314 142 321
31 412 513 614 715 816 917 18
11111111111111111111111111111 4 3