Tree Pigeon Numbering

You are given a tree with ( n ) nodes. The tree has ( n-1 ) edges and each node has a pigeon. You are required to assign each pigeon a unique number ( p_i ) (a permutation of ( {1,2,\dots,n} )) so that for every edge connecting nodes ( u ) and ( v ) the following inequality holds: [ p_u + p_v \le n+1 ] It can be shown that at least one valid assignment exists.

A key observation is that for any edge, if one endpoint is assigned a large number then the other must be assigned a very small number so that their sum does not exceed ( n+1 ). This motivates the following constructive strategy:

1. Root the tree at node 1 and determine the level (distance modulo 2) of each vertex. Let the set of vertices at even levels be ( E ) and at odd levels be ( O ).
2. If ( |E| \ge |O| ), assign the vertices in ( E ) (even levels) with the largest ( |E| ) numbers from ( {1,2,\dots,n} ) in descending order, and assign the vertices in ( O ) with the smallest ( |O| ) numbers in ascending order.
3. Otherwise (if ( |E| < |O| )), assign the vertices in ( E ) with the smallest ( |E| ) numbers in ascending order, and assign the vertices in ( O ) with the largest ( |O| ) numbers in descending order.

Why does this work? Consider the case when ( |E| \ge |O| ). An edge always connects one vertex in ( E ) and one in ( O ). In ( E ) the numbers come from a set ( L = {n-|E|+1,\dots,n} ) (so its minimum is ( n-|E|+1 )); in ( O ) the numbers come from a set ( S = {1,2,\dots,|O|} ) (its maximum is ( |O| )). For any edge, the worst‐case sum is ( (n-|E|+1) + |O| ). Since ( |E|+|O| = n ) and ( |O| \le |E| ) the inequality [ (n-|E|+1)+|O| \le n+1 ] holds. A similar check works in the other case.

Your task is to output a valid permutation ( p_1,p_2,\dots,p_n ) that satisfies the above condition.

Input Format:

• The first line contains an integer \( n \) representing the number of nodes.
• Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \) denoting an edge between nodes \( u \) and \( v \).

Output Format:

• Output a single line with \( n \) integers \( p_1, p_2, \dots, p_n \) separated by spaces.

Example: For example, consider the tree with ( n = 4 ) and edges:

1 2
2 3
3 4

A possible assignment is:

p = [4, 1, 3, 2]

Check the edges:

• Edge (1,2): 4+1=5 \(\le 4+1=5\)
• Edge (2,3): 1+3=4 \(\le 5\)
• Edge (3,4): 3+2=5 \(\le 5\)

Note: The input describes a tree so it is guaranteed to be connected and acyclic.

inputFormat

The first line contains a single integer ( n ) (( 2 \le n \le 10^5 )). Each of the next ( n-1 ) lines contains two integers ( u ) and ( v ) (( 1 \le u,v \le n )) denoting an undirected edge of the tree.

outputFormat

Output one line containing ( n ) space-separated integers, where the ( i )-th integer is the number assigned to the pigeon on node ( i ). The assignment must be a permutation of ( {1,2,\dots,n} ) and satisfy ( p_u+p_v \le n+1 ) for every edge ( (u,v) ).

sample

4
1 2
2 3
3 4

4 1 3 2