← 返回题目
题库练习 [ABC146D] Coloring Edges on Tree
← 上一题 下一题 →

A7556 | [ABC146D] Coloring Edges on Tree

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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

现在要用若干种颜色对 $G$ 的边进行染色。要求对于每个顶点，与该顶点相连的所有边的颜色都互不相同。

请构造一种满足上述条件的染色方案，并且所用颜色的种类数最少。

输入格式

输入以以下格式从标准输入读入。

> $N$
> $a_1$ $b_1$
> $a_2$ $b_2$
> $\vdots$
> $a_{N-1}$ $b_{N-1}$

输出格式

输出共 $N$ 行。

第 $1$ 行输出所使用的颜色数 $K$。

接下来的 $N-1$ 行，第 $i+1$ 行输出第 $i$ 条边的颜色，用整数 $c_i$ 表示。这里 $1 \leq c_i \leq 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
C++ 编辑器
输入
输出