题目描述

Given is a tree $G$ with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$-th edge connects Vertex $a_i$ and Vertex $b_i$.

Consider painting the edges in $G$ with some number of colors. We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

给出一棵树 $G$ ，有 $N$ 个顶点。顶点的编号为 $1$ 到 $N$ ， $i$ -th 边连接顶点 $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$ 必须保持不变。

如果有多个颜色的最小数量都满足条件，那么打印任何一个都会被接受。

样例 #1

样例输入 #1

3
1 2
2 3

样例输出 #1

2
1
2

样例 #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

样例输入 #3

6
1 2
1 3
1 4
1 5
1 6

样例输出 #3

5
1
2
3
4
5

说明

数据规模与约定

• $2 \le N \le 10^5$
• $1 \le a_i \lt b_i \le N$
• 输入值均为整数。
• 给定图形是一棵树。