/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
N 頂点の木 G が与えられます。 頂点には 1 から N までの番号がついており、i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。
G の辺を何色かで塗り分けることを考えます。 このとき、各頂点について、その頂点を端点に持つ辺の色がすべて相異なるようにしたいです。
上記の条件を満たす塗り分けの中で、使用する色の数が最小であるようなものを 1 つ構築してください。
制約
- 2 \le N \le 10^5
- 1 \le a_i \lt b_i \le N
- 入力はすべて整数
- 与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}
出力
出力は N 行からなる。
1 行目に使用する色の数 K を出力せよ。
i+1 行目 (1 \le i \le N-1) に i 番目の辺の色を表す整数 c_i を出力せよ。ここで 1 \le c_i \le K でなければならない。
問題文中の条件を満たし、使用する色の数が最小であるような塗り分けが複数存在するときは、そのうちのどれを出力しても構わない。
入力例 1
3 1 2 2 3
出力例 1
2 1 2
入力例 2
8 1 2 2 3 2 4 2 5 4 7 5 6 6 8
出力例 2
4 1 2 3 4 1 1 2
入力例 3
6 1 2 1 3 1 4 1 5 1 6
出力例 3
5 1 2 3 4 5
Score : 400 points
Problem Statement
Given is a tree G with N vertices. The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.
Consider painting the edges in G with some number of colors. We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.
Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.
Constraints
- 2 \le N \le 10^5
- 1 \le a_i \lt b_i \le N
- All values in input are integers.
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}
Output
Print N lines.
The first line should contain K, the number of colors used.
The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.
If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.
Sample Input 1
3 1 2 2 3
Sample Output 1
2 1 2
Sample Input 2
8 1 2 2 3 2 4 2 5 4 7 5 6 6 8
Sample Output 2
4 1 2 3 4 1 1 2
Sample Input 3
6 1 2 1 3 1 4 1 5 1 6
Sample Output 3
5 1 2 3 4 5