Hide

Problem O
Sneaky Exploration

You have been sent to spy on the city of Galcary. When you arrive, you realize with shock that the Galcarians are far more efficient than you first expected. Every pair of buildings in Galcary are connected by some sequence of roads (roads go between two buildings), and the Galcarians have built the minimum number of roads possible to achieve this. You decide you must learn more by visiting every building.

You may start and end in any building you wish, but you may not visit the same building twice as you are on a strict schedule. Your method of choice to avoid detection is flying between buildings. If you fly over a road built by the Galcarians, the risk of detection by Galcary’s anti-spy force is too high. So you may not travel directly between buildings connected by a road.

Input

The first line of input contains a single integer $N$ ($1 \leq N \leq 100\, 000$), indicating the number of buildings in Galcary. Then $N-1$ lines follow, each containing two integers $u$ and $v$ ($1 \leq u < v \leq n$), indicating there is a road between $u$ and $v$.

It is guaranteed that all buildings are connected to all other buildings by some sequence of roads.

Output

If there is a way to explore Galcary adhering to the specifications above, print any such exploration on one line - this takes the form of $N$ space-separated integers indicating the order in which you visit buildings. The printed numbers must be a permutation of $\{ 1, 2, \ldots , N\} $, and each adjacent pair of buildings must not have a road between them.

If there is no such way to explore Galcary, output a single integer $-1$.

Sample Input 1 Sample Output 1
4
1 2
2 3
3 4
3 1 4 2 
Sample Input 2 Sample Output 2
4
1 2
2 3
2 4
-1
Sample Input 3 Sample Output 3
5
1 2
2 3
2 5
3 4
2 4 5 3 1 

Please log in to submit a solution to this problem

Log in