TAP2012F - Fixture

no tags 

[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/taip2012-problems.pdf]

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.

 

Input

Each test case is described using two lines. The first line contains a single integer number N, representing the number of competitors ( 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 most 100 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.

 

Output

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.

 

Example

Input:
4
314 142 321
9
31 412 513 614 715 816 917 18
4
11111111111111111111111111111 4 3
-1

Output:
324
98765432
22222222222222222222222222222

hide comments
:D: 2012-10-29 07:07:19

You probably meant "I pass every sample test case". Witch is very different from solving the problem. Sample isn't there to help you debug (most of the time). It's just to help you understand the problem.

I wouldn't say there's anything tricky, at least for my approach there wasn't.

fersarr: 2012-10-26 06:29:56

Are there any tricky cases? I pass every test but I get wrong answer

:D: 2012-10-10 11:37:16

It's a little spoiling, so don't read if you understand the problem:

.
.
.

Before 2 can match with 1 it must match with 3, but before 3 can match with 2, it must match with 5 and 1. In conclusion match 1-3 must come before 1-2.

Pranay: 2012-10-09 03:27:27

why can't order for case 2 be 92345678 ?

Thanks zukow :) was not able to understand the chronological order properly

Last edit: 2012-10-10 15:41:55

Added by:Fidel Schaposnik
Date:2012-10-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2012