409570: GYM103634 A Bamboo Coloring

You are given a tree with $$$N$$$ nodes and $$$N-1$$$ undirected edges. You will to find the lexicographically minimal bamboo coloring of the given tree. A bamboo coloring of a tree satisfies all of the following constraints:

• Each node $$$u \in [1,N]$$$ is colored with a color $$$c_u \in [1,N]$$$;
• Each node $$$u \in [1,N]$$$ is adjancent to at most $$$2$$$ other nodes with the same color as $$$u$$$;
• For each color $$$c \in [1,N]$$$, all nodes colored with color $$$c$$$ form a connected component of the tree.

The first line of input contains one integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the number of nodes in the tree.

Each of the next $$$N-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$), meaning that there exists an undirected edge between nodes $$$u$$$ and $$$v$$$.

It is guaranteed that the graph given in the input forms a tree.

Print $$$N$$$ integers $$$c_1,c_2,\ldots, c_n$$$ ($$$1 \le c_i \le N$$$) coresponding to the lexicographically minimal bamboo coloring of the given tree, where $$$c_u$$$ ($$$u \in [1,N]$$$) represents the color of node $$$u$$$.

8
1 2
1 3
1 4
1 5
4 7
4 8
5 6

1 1 1 2 3 3 2 2 

9
1 9
9 2
9 7
7 6
7 8
7 4
6 3
6 5

1 1 2 2 3 2 2 4 1 

The tree from the first sample

In this image, color $$$1$$$ is represented by green, color $$$2$$$ by blue, and color $$$3$$$ by yellow.