Alternative formats: PostScript

The International X-Game Federation organises a tournament in which programmes that play this game participate. n programmes numbered from 1 to n take part in the competition. The rules of the tournament are as follows: while there remains more than one programme in the tournament, two of them (distinct) are randomly chosen to play a game. The defeated one (there are no draws in the X-Game) drops out of the tournament and the whole procedure is repeated. The sole programme which stays in the tournament after all n-1 games have been played is the winner.

The fedaration has a table of results of previous tournaments. It is known, that the programmes play deterministicly (i.e. in repeatable fashion) and in exactly the same way as in previous tournaments. So, if two programmes have already played one against another then their next game will end with the same result. If, however, they have never played against each other, the outcome of the game cannot be predicted - both have a chance of winning. The federation would like to know a list of all programmes which have a chance of winning the tournament.

Task

Write a programme which:

• reads from the standard input the number of participating programmes and the table of results of their previous games,
• determines all programmes which have a chance of winning the tournament,
• writes the outcome to the standard output.

Input

The first line of the input contains an integer n, 1 <= n <= 100.000. The next n lines contain the table of results of previous games: i+1st line contains an integer k_i, 0 <= k_i < n, followed by k_i numbers of programmes, not equal to i, in increasing order - those are the numbers of programmes, with which the programme i has previously won. The numbers in lines are separated by single spaces. The number of all known results of previous games does not exceed 1.000.000.

Output

Example

For the input data:

4
2 2 3
0
1 2
1 2

the correct outcome is:

3 1 3 4

Print friendly version