Martian Domino
Upon returning home from another expedition to Mars, Vasya brought back a suitcase filled with mysterious stone rectangles. Each rectangle was twice as long as it was wide and was divided by a line into 2 squares. Each square had a symbol drawn on it, and there was 1 symbol on the reverse side.
Vasya struggled for a long time to unravel the mystery of these rectangles. One night, he woke up realizing he had finally solved the puzzle. It turns out the symbols on top are numbers from 1 to n, and the rectangles are domino pieces. The symbol on the bottom represents the price of the domino.
Now Vasya is troubled by the question: is it possible to form a chain with all these pieces according to the rules of dominoes? Moreover, he wants to sleep, so he can't handle it on his own. Help Vasya solve this problem.
Input
The first line of the input contains a natural number n - the maximum number written on the top surface of the domino piece (1 ≤ n ≤ 1000). Then follow n lines describing the domino pieces. In the i-th of these lines, there is a number m_i - the number of domino pieces containing the number i. Next, there are m_i pairs of positive numbers: the first is the number written on the second half of the domino piece, and the second number is its price.
There may be several identical domino pieces, but there is none with the same number written on both ends.
All numbers in the input do not exceed 10^5; it is guaranteed that the total number of domino pieces is at least one and does not exceed 10^5.
Output
If a solution exists, output one number in the first line of the output - the number of domino pieces in the desired chain (counting the first and last), and in the second line - the numbers in the order they will be in the chain (output the connection point of the domino pieces as one number - see example).
If there are no solutions, output the number -1.
If there are multiple solutions, output any one.