题目描述

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

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

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

输入

第一行一个整数$N$

接下来一共$N-1$行，分别表示$a_i,b_i$

输出

输出 $N$ 行。

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

第 $(i+ 1)$ 行$(1 <i< N - 1)$应包含一个整数 $c_i$，表示第$i$条边的颜色，其中必须满足$1 \leq c \leq 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$
• 给定的图是一颗树