问题描述

给定一棵具有 $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$。

如果满足条件的最少颜色数的着色方案有多个，任何一个都可以接受。

示例输入 1

3
1 2
2 3

示例输出 1

2
1
2

示例输入 2

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

示例输出 2

4
1
2
3
4
1
1
2

示例输入 3

6
1 2
1 3
1 4
1 5
1 6

示例输出 3

5
1
2
3
4
5