D - 树上染色(缺少SPJ)

得分：$400$ 分

问题描述

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

考虑使用一些颜色对 $G$ 中的边进行染色。 我们希望染色的要求是对于每个顶点，与该顶点相邻的边的颜色都不相同。

在满足上述条件的染色方案中，构造一个使用颜色数量最小的方案。

约束

• $ 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$ 行。

第一行应包含使用的颜色数量 $K$。

第 $(i+1)$ 行 $(1 \le i \le N-1)$ 应包含一个整数 $c_i$，表示第 $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