刘老师要给一棵树的每条边涂上一种颜色。树共有 $N$ 个顶点和 $N-1$ 条边，边按照输入顺序编号为 $1$ 到 $N-1$。

如果两条边拥有同一个端点，就称这两条边相邻。相邻的两条边不能使用同一种颜色。刘老师希望使用的颜色种类数尽可能少，颜色用从 $1$ 开始的正整数表示。

为了使输出结果唯一，本题采用下面的固定输出约定：从顶点 $1$ 开始进行深度优先遍历；在每个顶点处，按照输入边编号从小到大处理尚未访问的相邻顶点；为通向孩子的边选择从 $1$ 开始、既不等于父边颜色，也没有在当前顶点使用过的最小颜色。

请输出所需的最少颜色数，以及按照上述约定得到的每条边的颜色。

输入格式

第一行输入一个整数 $N$，表示树的顶点数量。

接下来 $N-1$ 行，第 $i$ 行输入两个整数 $a_i$ 和 $b_i$，表示编号为 $i$ 的边连接顶点 $a_i$ 和顶点 $b_i$。

输出格式

第一行输出一个整数 $K$，表示使用的最少颜色数。

接下来 $N-1$ 行，第 $i$ 行输出一个整数，表示编号为 $i$ 的边所使用的颜色。

5
2 1
1 4
5 3
3 1

3
1
2
1
3

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

4
1
1
2
3
2
2
4
4

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

3
1
2
1
1
3
2
2

数据范围与约定

• $2\le N\le10^5$
• 输入图是一棵树