Traveling Saga

Time limit3sMemory limit256 MB

Summary

Print the order in which an apple from vertex 1 visits every tree vertex by always moving to the farthest unvisited vertex, breaking ties by largest index.

Level: Medium7 of 10
Topics: Tree, Segment tree, Greedy
Solved: No attempts yet

Problem

An unweighted tree with $n$ vertices holds one apple, starting at vertex 1.

The apple wants to visit every vertex exactly once. At each step it moves to the unvisited vertex farthest from its current position. If several vertices tie for farthest, it chooses the largest index.

Print the visit order.

Input

Line 1: $n$ ( $1 \le n \le 250000$ ).

Next $n-1$ lines: edges $s$ and $e$ ( $1 \le s, e \le n$ , $s \ne e$ ). The graph is a tree.

Output

Print the visited vertex numbers separated by spaces.

Examples1

Example 1

Input

Expected output

1 7 4 6 3 5 2