atcoder#ARC117D. [ARC117D] Miracle Tree

[ARC117D] Miracle Tree

Score : 600600 points

Problem Statement

We have a tree with NN vertices, numbered 1,2,,N1, 2, \dots, N. The ii-th edge (1iN1)(1 \leq i \leq N-1) connects Vertex AiA_i and Vertex BiB_i.

A boy E869120 found this tree and wants to write an integer in each vertex to surprise another boy square1001. For that, the following conditions need to be satisfied, where EiE_i is the integer written on Vertex ii.

Condition 1: Ei1E_i \geq 1 (1iN)(1 \leq i \leq N) holds. Condition 2: EiEjdist(i,j)|E_i - E_j| \geq dist(i, j) holds for every pair (i,j)(i, j) (1i<jN)(1 \leq i < j \leq N). Condition 3: the value max(E1,E2,,EN)\max(E_1, E_2, \dots, E_N) should be minimized while satisfying Conditions 1 and 2.

Here, dist(i,j)dist(i, j) is:

  • the length of the simple path (the path without repetition of the same vertex) from Vertex ii to jj.
  • In other words, it is the value LL where the simple path is q0q1q2qLq_0 \to q_1 \to q_2 \to \cdots \to q_L (q0=i,qL=jq_0 = i, q_L = j).

Construct one way to write integers that surprises square1001.

Constraints

  • 2N2000002 \leq N \leq 200000
  • 1Ai<BiN1 \leq A_i < B_i \leq N
  • The given graph is a tree.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN

A1A_1 B1B_1

A2A_2 B2B_2

\vdots

AN1A_{N-1} BN1B_{N-1}

Output

Print a line containing integers E1,E2,,ENE_1, E_2, \cdots, E_N to write on the vertices, in this order, with space as separator.

If there are multiple ways to write integers that satisfy the conditions in the Problem Statement, any of them will be accepted.

E1E_1 E2E_2 \cdots ENE_{N}

2
1 2
2 1

If we write an integer 22 on Vertex 11 and an integer 11 on Vertex 22, we have dist(1,2)=1dist(1, 2) = 1 and E1E2=1|E_1 - E_2| = 1, satisfying Condition 2.

The other conditions are also satisfied, so we can surprise square1001 this way.

(E1,E2)=(1,2)(E_1, E_2) = (1, 2) will also be accepted.

4
1 2
1 4
2 3
3 2 1 4

(E1,E2,E3,E4)=(2,3,4,1)(E_1, E_2, E_3, E_4) = (2, 3, 4, 1) will also be accepted.