J9 习题-6 树上染色

题目描述

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

考虑用一些颜色绘制 $G$ 的边。我们想要绘制它们，这样，对于每个顶点，与该顶点相关的边的颜色都是不同的。

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

输入格式

第一行，一个整数 $N$，表示树的顶点个数；

第二行到第 $N$ 行，每行两个整数 $a_i$ 和 $b_i$，表示有条边连接顶点 $a_i$ 和顶点 $b_i$。

输出格式

输出一共 $N$ 行。

第一行应该包含K，即使用的颜色数。

第$i+1$行（ $1 \le i \le N-1$ ）应包含c_i，表示第 $i$条边颜色的整数，其中 $1\le c_i \le K$，边的编号越小的边的颜色编号越小。

样例输入1

3
1 2
2 3

样例输出2

2
1
2

样例输入3

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

样例输出4

4
1
2
3
4
1
1
2

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$2 \le N \le 10^5$。