Description

HWX is well-known in the computer group for his love of geometry and is reputed to "solve every problem." One day, while LXC was playing with Logo, he suddenly thought of a problem that could test HWX’s reputation. He used Logo to draw an $n$-gon and casually labeled its $n$ vertices with the consecutive natural numbers $1, 2, 3, \ldots, n$. To increase the difficulty, he also drew some non-intersecting diagonals. As shown in the figure:

He wrote down all the sides and diagonals on a piece of paper. For the figure above, he wrote: $(1, 3)$, $(3, 2)$, $(2, 4)$, $(4, 5)$, $(5, 1)$, $(1, 4)$, $(3, 4)$. Just when he was pleased with himself, the computer suddenly rebooted automatically. Unfortunately, he had forgotten to save the Logo program. Now he wants to use the recorded information on the paper to restore the labeling of the $n$-gon. Can you help him?

Input Format

The first line contains $n$ ($n \le 50$).

The following lines each contain two integers $a, b$, representing one recorded segment (either a side or a diagonal). Input continues until EOF.

Output Format

Output a single line listing the labels of the vertices in order around the polygon. If both directions are possible, output the lexicographically smaller sequence. For the example above, your output should be 1 3 2 4 5.

5
1 3
3 2
2 4
4 5
5 1
1 4
3 4

1 3 2 4 5

Hint

Translated by ChatGPT 5