Mailman#1946
In the city, there are squares connected by streets. The total number of streets does not exceed , and at most three squares have an odd number of streets connected to them. Each street has a known length and can be traveled in both directions. There is at least one street in the city, and you can reach any square from any other square using the streets.
The postman needs to walk along each street at least once, aiming to minimize the total length of his route. He can start and finish his journey at any square, including the same square.
The first line of the input contains a natural number — the number of squares in the city (1 \leq n \leq 1000).
Following this are lines that describe the streets. In the -th line, there is a number m_i — the number of streets leading from square . This is followed by m_i pairs of positive numbers. In the -th pair, the first number indicates the square to which the -th street from square leads, and the second number is the length of this street.
There may be multiple streets between two squares, but no street leads from a square to itself.
All numbers in the input do not exceed 10^5.
If a solution exists, output a single number on the first line — the number of streets in the desired route (including the first and last), and on the second line — the sequence of square numbers in the order they are visited.
If no solution exists, output the number .
If there are multiple solutions, you may output any one of them.
Example 1