Andryusha and Colored Balloons
Contest: Технокубок 2017 - Финал (только для онсайт-финалистов)
Difficulty rating: 1600
Tags: dfs and similar, graphs, greedy, trees

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!

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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

Illustration for the second sample.

In the third example there are following triples:

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

Illustration for the third sample.

Example input:
3
2 3
1 3

Example output:
3
1 3 2

Example input:
5
2 3
5 3
4 3
1 3

Example output:
5
1 3 2 5 4

Editorial:
If v is a vertex of degree d, then the answer is at least d + 1. Indeed, any two neighbours of v can be connected by a path of length three via vertex v. Also, v lies on a common three-vertex path with any of its neighbours (possibly using a non-neighbour vertex). It follows that v and all of its neighbours must have pairwise distinct colors.
Let us show that the strongest of these estimates is best possible, that is, construct a coloring with D + 1 colors, where D is the maximal degree. Root the tree at arbitrary vertex, and color the root with color 1, also color its children with subsequent colors. All the rest vertices will be colored as follows: if a vertex v is colored x, and its parent is colored y, then for the children of v we will use numbers starting from 1 skipping x and y. One can check that no color with number larger than D + 1 shall be used. Implementation-wise, this is a simple DFS procedure.
Complexity: O(n) time and memory.