题目描述

$N$ 頂点の木 $G$ が与えられます。 頂点には $1$ から $N$ までの番号がついており、$i$ 本目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

$G$ の辺を何色かで塗り分けることを考えます。 このとき、各頂点について、その頂点を端点に持つ辺の色がすべて相異なるようにしたいです。

上記の条件を満たす塗り分けの中で、使用する色の数が最小であるようなものを $1$ つ構築してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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

提示

制約

• $2\ \le\ N\ \le\ 10^5$
• $1\ \le\ a_i\ \lt\ b_i\ \le\ N$
• 入力はすべて整数
• 与えられるグラフは木である