Description

Xiaoming's lab has $N$ computers, numbered $1 \sim N$. Originally, there were $N-1$ data links connecting these $N$ computers, forming a tree network. In a tree network, there is a unique path between any two computers.

However, during a recent network maintenance, the administrator made a mistake and added one extra data link between two computers, so a cycle appeared in the network. For the computers on the cycle, since there is no longer only one path between each pair of them, data transmission on these computers has bugs.

To restore normal transmission, Xiaoming needs to find all computers that are on the cycle. Can you help him?

Input Format

The first line contains an integer $N$.

The following $N$ lines each contain two integers $a$ and $b$, indicating that there is a data link between $a$ and $b$.

The input is guaranteed to be valid.

Output Format

Output the numbers of the computers on the cycle in increasing order, separated by a single space.

5
1 2
3 1
2 4
2 5
5 3

1 2 3 5

Hint

For $30\%$ of the testdata, $1 \le N \le 1000$.

For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le a,b \le N$.

Time limit: 1 second, 256 MB. Lanqiao Cup 2017, the 8th National Contest.

Translated by ChatGPT 5