402814: GYM100886 I Archaeological Research

Professor Tupids has found a mysterious manuscript during his recent archaeological expedition.

The manuscript, in fact, looks like a series of symbols with meaning yet to be discovered. In order to simplify studying of the manuscript, professor Tupids created an alphabet of all symbols occurred (let's denote their number as c) and replaced each symbol with its position in the alphabet (positions are numbered from one). So, the manuscript became represented as a list of n integers from the segment [1;c].

Professor's intuition told him that the key to understanding the manuscript is to find some regularities in locations of the symbols. So he wrote down a huge table with n rows and c columns, where cell at i-th row and j-th column contained the position of the next occurrence of symbol number j after the position i (the cell was left empty if there were no appropriate occurrences).

But then a disaster happened: a fire in the laboratory completely destroyed the manuscript! Fortunately, the table built by professor was salvaged, though it was damaged to some extent. Not only some of the cells were lost in the fire, but, thanks to the careless assistants, cells in each of the rows were reordered arbitrarily!

Professor Tupids doesn't want to lose face in the scientific community, so he asks you to help him with restoring the original manuscript, given the remaining information from the table. As there may be infinitely many different solutions (even the size c of the alphabet was lost!), professor wants you to restore the lexicographically smallest solution. It is not guaranteed that the solution exists, though, as the table could have been completely spoiled by the assistants.

The first line contains a single integer n (1 ≤ n ≤ 3·10⁵), the length of the original manuscript. After that, n lines follow, the i-th of which contains an integer c_i (0 ≤ c_i ≤ n - i) followed by c_i distinct integers from the segment [i + 1;n]: the contents of the survived non-empty cells of the i-th row of the table in arbitrary order.

It is guaranteed that the sum of all c_i (1 ≤ i ≤ n) does not exceed 3·10⁵.

If the solution exists, print a single line with n positive integers: the representation of the lexicographically smallest manuscript. Otherwise, print "No solution" (without quotes).

4
3 2 3 4
2 4 3
1 4
0

1 1 2 3 

5
1 2
1 4
1 4
1 5
0

1 1 1 2 1