| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 22 | 2 | 2 | 9.091% |
The kindergarten founded by Finley Marlin is attended by exactly 2ドルn$ children. Today they have a party and the kids will dance around the large palm tree in the center of the room. There are young kids involved, so there are some restrictions on how the event would be organized.
For example, every kid has the best friend, and every kid is also the best friend of his best friend. If we consider pairs of best friends, they will be kids with numbers 2ドルi - 1$ and 2ドルi$. Kids refuses to participate in the dance if they are not standing next to their best friend.
The kid number $i$ came to the party wearing outfit $x_i,ドル but there can be some identical outfits worn by different children. So if two kids are not best friends and they wear the same outfits, they refuse to stand next to each other. Friendship is stronger than fashion, so best friends agree to stand next to each other even if they wear the same outfit.
Please help the tired teachers to place as much children as possible into the circle so that all the demands of children standing in circle are satisfied.
The first line of input contains one integer $n$ --- the number of pairs of children (1ドル \leq n \leq 300,000円$).
Each of the following $n$ lines contains two integers: the $i$-th line contains $x_{2i-1}$ and $x_{2i}$ --- the outfits worn by the $(2i-1)$-th and the 2ドルi$-th kids respectively (1ドル \leq x_{2i-1}, x_{2i} \leq 2n$).
The first line of output must contain $k$ --- the maximum number of pairs of children that can form the circle. Even one pair can form a circle.
The next line should contain space-separated numbers of children in the circle in the order they are standing.
If there are several optimal answers output any of them.
3 1 1 1 2 1 3
2 3 4 5 6
4 1 2 3 4 4 2 1 3
4 1 2 3 4 6 5 7 8