Problem Description

Given a rooted tree with $n$ nodes, where the root node is numbered as $1$. Let $T_i$ denote the subtree rooted at node $i$. You need to assign each node a positive integer node weight $v_i$ such that all node weights are exactly $1, 2, \dots, n$ each occurring once. Define
$$f = \sum_{i=1}^{n} R_i,$$
where $R_i$ is the range of node weights in the subtree rooted at $i$, i.e.,
$$R_i = \max_{j \in T_i} \{v_j\} - \min_{j \in T_i} \{v_j\}.$$
For all possible ways of assigning node weights, find a set of node weights that minimizes $f$.

Input Format

The first line contains a positive integer $n$, representing the number of nodes in the tree.

The next $n-1$ lines each contain two positive integers $u$ and $v$, indicating that there is an edge between nodes $u$ and $v$.

Output Format

The first line should contain a permutation of $1, 2, \dots, n$, representing the node weights for nodes $1, 2, \dots, n$. Since there may be multiple ways to assign node weights, you only need to output any one of them.

Sample Input and Output

Sample Input #1

3
1 2
1 3

Sample Output #1

1 2 3

Sample Input #2

2
1 2

Sample Output #2

1 2

Sample Input #3

5
1 2
2 3
3 4
4 5

Sample Output #3

1 2 3 4 5

Notes

Sample Explanation

Input #1

$R_1 = 3 - 1 = 2, R_2 = 2 - 2 = 0, R_3 = 3 - 3 = 0, f = R_1 + R_2 + R_3 = 2$. It can be proven that there is no construction that results in a smaller $f$.

Data Range

For $10\%$ of the data, $n \le 10$;

For another $10\%$ of the data, the tree is a chain;

For another $20\%$ of the data, there is a node connected to all other $n-1$ nodes;

For another $20\%$ of the data, the tree is a complete binary tree, where each node, except for the leaf nodes, has exactly two children;

For $100\%$ of the data, $1 \le n \le 10^6$.

见题面 Input 部分

见题面 Output 部分