I. Saki and Encoding
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Saki is interested in various ways to encode a tree into a sequence ever since she has invented Tree++, especially the Prüfer sequence.

Given a tree with $$$N$$$ nodes labelled from $$$0$$$ to $$$N-1$$$, the Prüfer sequence of the tree is the sequence obtained by the following process.

  1. Initialize the sequence to be empty.
  2. Repeat the following $$$N-2$$$ times: pick the leaf with the smallest label, append to the sequence the only neighbor of the leaf, and then erase the leaf along with the only edge connected to it.
Note that after this process, exactly two nodes remain. Let's define the waste as the sum of their labels.

Saki is curious about how much waste will be made on a given tree with nodes numbered from $$$0$$$ to $$$N-1$$$, so she will perform the following action for each $$$k=0, \cdots, N-1$$$.

  1. Assign label $$$(u+k) \mod N$$$ to the node numbered $$$u$$$.
  2. Record the waste $$$W_k = (\text{the waste of the current labelling})$$$.

Saki is very busy, so she has asked you for a favor. Write a program to help Saki compute $$$W_k$$$ for each $$$0 \le k \lt N$$$.

Input

The input is given in the following format:

$$$N$$$
$$$U_0$$$$$$V_0$$$
$$$U_1$$$$$$V_1$$$
$$$\vdots$$$
$$$U_{N-2}$$$$$$V_{N-2}$$$

where $$$N$$$ is the number of the nodes in the tree, and the $$$i$$$-th edge connects the nodes $$$U_i$$$ and $$$V_i$$$ for all integer $$$0 \le i \lt N-1$$$.

The input satisfies the following constraints:

  • All numbers in the input are integers.
  • $$$2 \le N \le 1\,000\,000$$$ ($$$= 10^{6}$$$)
  • $$$0 \le U_i, V_i \lt N$$$
  • The edges given in the input form a valid tree.
Output

The output should be in the following format:

$$$W_0$$$
$$$W_1$$$
$$$\vdots$$$
$$$W_{N-1}$$$

where $$$W_k$$$ is the waste of the tree when node $$$u$$$ is labelled with $$$u+k \mod N$$$.

Example
Input
7
0 3
0 4
0 6
1 4
2 4
3 5
Output
6
10
8
9
7
8
11