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
第三个示例的插图。