Mykola, Vasyl and a maze
Limits: 2 sec., 256 MiB
The Office of «Extralogic» is a real maze. Builders Vasyl and Mykola do not only can’t find a room, they have to paint the door, and got lost!
In order to somehow help the poor builders, the kind employees of «Extralogic» handed an office plan to Mykola and Vasyl. According to the plan, the office consists of n rooms, some of which are connected by a passage. There are n such passages. Each passage is bidirectional. It is guaranteed that there is a path between any pair of rooms in the office, and that there is no more than one passage between any pair of rooms in the office.
Mykola and Vasyl remember that they had to draw a door to one of the rooms, which is located in a cycle. A cycle is a sequence of different office rooms a1,a2,...,ak, that includes a passage between rooms a1 and a2, a2 and a3, ..., ak−1 and ak, ak and a1. Help builders find lists of all office rooms that belong in at least one cycle.
Input
First line contains one integer n – number of rooms in the ofice.
Next n lines contain two integers ai and bi – describes i-th passage between rooms ai and bi.
Output
In first line print one integer k – number of rooms which belongs to at least one cycle.
In second line print k integers – indecies of rooms in ascening order.
Constraints
30% tests: 3≤n≤100.
70% tests: 3≤n≤105.
For all tests: 1≤ai,bi≤n.
Samples
Input (stdin) | Output (stdout) |
---|---|
4 1 2 2 3 3 4 4 2 | 3 2 3 4 |
Notes
Rooms 2, 3 and 4 belong to a cycle. Room 1 does not belong to any cycle.