← 返回题目列表

AtCoder · abc146_d

D. 给树上的边缘着色

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给定的是一棵树 G 与 N 顶点。 顶点已编号 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