← 返回题目列表

Codeforces · 780/C

C. Andryusha 和彩色气球

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

Andryusha 每天都会经过一个公园。它们之间的广场和小路对 Andryusha 来说看起来很无聊,所以他决定装饰它们。

公园由 n 个广场组成,这些广场通过 (n - 1) 条双向路径连接,使得任何广场都可以使用这些路径从任何其他广场到达。安德留莎决定在每个广场上挂一个彩色气球。气球的颜色用从 1 开始的正整数描述。为了让公园变得五彩缤纷,Andryusha 想要以特殊的方式选择颜色。更准确地说,他想要使用这样的颜色:如果 a、b 和 c 是不同的正方形,并且 a 和 b 之间有直接路径,并且 b 和 c 之间有直接路径,则这三个正方形上的气球颜色是不同的。

Andryusha 希望使用尽可能少的不同颜色。帮助他选择颜色!

输入

第一行包含单个整数 n (3 ≤ n ≤ 2·105) — 公园中的方块数量。

接下来的 (n - 1) 行包含两个整数 x 和 y (1 ≤ x, y ≤ n) - 通过路径直接连接的两个正方形的索引。

保证任何方格都可以使用路径从任何其他方格到达。

输出

在第一行中打印单个整数 k — Andryusha 必须使用的最小颜色数。

在第二行中打印n个整数,其中第i个整数应等于第i个正方形上的气球颜色。这些数字中的每一个都应该在 1 到 k 的范围内。

示例

输入 #1

3
2 3
1 3

输出 #1

3
1 3 2

输入 #2

5
2 3
5 3
4 3
1 3

输出 #2

5
1 3 2 5 4

输入 #3

5
2 1
3 2
4 3
5 4

输出 #3

3
1 2 3 1 2

注意

在第一个示例中,公园由三个正方形组成:1 → 3 → 2。因此,气球颜色必须不同。

第一个示例的插图。

在第二个示例中,有以下三元组的相应连接的正方形:

- 1 → 3 → 2
- 1 → 3 → 4
- 1 → 3 → 5
- 2 → 3 → 4
- 2 → 3 → 5
- 4 → 3 → 5

第二个示例的插图。

在第三个示例中,有以下三元组:

- 1 → 2 → 3
- 2 → 3 → 4
- 3 → 4 → 5

第三个示例的插图。