AT_abc146_d [ABC146D] 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$ 行。

第 $1$ 行输出所使用的颜色数 $K$。

接下来的 $N-1$ 行，第 $i+1$ 行输出第 $i$ 条边的颜色，用整数 $c_i$ 表示。这里 $1 \leq c_i \leq K$。

如果存在多种满足条件且颜色数最少的染色方案，可以输出其中任意一种。

样例 1

输入

3
1 2
2 3

输出

2
1
2

样例 2

输入

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

输出

4
1
2
3
4
1
1
2

样例 3

输入

6
1 2
1 3
1 4
1 5
1 6

输出

5
1
2
3
4
5

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $1 \leq a_i < b_i \leq N$
• 输入均为整数
• 给定的图一定是一棵树

由 ChatGPT 4.1 翻译