CF780C.Andryusha and Colored Balloons

Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.

The park consists of n squares connected with (n - 1) bidirectional paths in such a way that any square is reachable from any other using these paths. Andryusha decided to hang a colored balloon at each of the squares. The baloons' colors are described by positive integers, starting from 1. In order to make the park varicolored, Andryusha wants to choose the colors in a special way. More precisely, he wants to use such colors that if a, b and c are distinct squares that a and b have a direct path between them, and b and c have a direct path between them, then balloon colors on these three squares are distinct.

Andryusha wants to use as little different colors as possible. Help him to choose the colors!

安德柳沙每天都会穿过一个公园。公园里的广场及其之间的路径在安德柳沙看来十分单调，因此他决定对它们进行装饰。

该公园由 $n$ 个广场组成，这些广场通过 $(n-1)$ 条双向路径相互连接，且任意两个广场之间均可通过这些路径互相到达（即整个结构构成一棵树）。安德柳沙决定在每个广场上悬挂一个彩色气球。气球的颜色用正整数表示，从 $1$ 开始编号。为了使公园呈现丰富多彩的效果，安德柳沙希望以一种特殊的方式选择颜色。更准确地说，他希望所选颜色满足如下条件：若 $a$、$b$ 和 $c$ 是三个互不相同的广场，且 $a$ 与 $b$ 之间存在一条直接路径，$b$ 与 $c$ 之间也存在一条直接路径，则这三个广场上的气球颜色必须互不相同。

安德柳沙希望使用尽可能少的不同颜色。请帮助他完成颜色的选择！

The first line contains single integer n (3 ≤ n ≤ 2·105) — the number of squares in the park.

Each of the next (n - 1) lines contains two integers x and y (1 ≤ x, y ≤ n) — the indices of two squares directly connected by a path.

It is guaranteed that any square is reachable from any other using the paths.

第一行包含一个整数 $n$（$3 \leq n \leq 2 \cdot 10^5$）——公园中广场的数量。

接下来的 $(n - 1)$ 行中，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n$）——由一条路径直接相连的两个广场的编号。

保证任意两个广场之间均可通过路径互相到达。

In the first line print single integer k — the minimum number of colors Andryusha has to use.

In the second line print n integers, the i-th of them should be equal to the balloon color on the i-th square. Each of these numbers should be within range from 1 to k.

第一行输出一个整数 $k$ —— Andryusha 所需使用的最少颜色数。

第二行输出 $n$ 个整数，其中第 $i$ 个数表示第 $i$ 个方格上气球的颜色。这些数均应在 $1$ 到 $k$ 的范围内。

In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct.

Illustration for the first sample.

In the second example there are following triples of consequently connected squares:

• 1 → 3 → 2
• 1 → 3 → 4
• 1 → 3 → 5
• 2 → 3 → 4
• 2 → 3 → 5
• 4 → 3 → 5

We can see that each pair of squares is encountered in some triple, so all colors have to be distinct.

Illustration for the second sample.

In the third example there are following triples:

• 1 → 2 → 3
• 2 → 3 → 4
• 3 → 4 → 5

We can see that one or two colors is not enough, but there is an answer that uses three colors only.

Illustration for the third sample.

在第一个样例中，公园由三个方块组成：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

可以看出，仅使用一种或两种颜色是不够的，但存在一种仅需三种颜色的方案。

第三个样例的示意图。