树的边染色

题目描述

给定有 $N$ 个顶点的树 $G$。 顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。

考虑用若干种颜色给 $G$ 的边染色。 此时，希望对于每个顶点，以该顶点为端点的所有边的颜色互不相同。

请在满足上述条件的染色方案中，构造一种使用颜色数最少的方案。

输入格式

输入按以下格式从标准输入给出：

$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$
• 输入均为整数
• 给定的图是一棵树

提示

答案不唯一，输出任意合法解即可。