配点 : $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$ でなければならない。

問題文中の条件を満たし、使用する色の数が最小であるような塗り分けが複数存在するときは、そのうちのどれを出力しても構わない。

3
1 2
2 3

2
1
2

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

4
1
2
3
4
1
1
2

6
1 2
1 3
1 4
1 5
1 6

5
1
2
3
4
5