Coloring Edges on Tree

题目描述

给定一个有 $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$ 行。 第一行应包含 $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

提示

$2 \le N \le 10^5$ $1 \le a_i \lt b_i \le N$ 输入中的所有值均为整数。 给定的图是树。

标签: AtCoder|abc146D

来源

AtCoder|abc146D