Tiles Placement
Contest: Codeforces Round 583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)
Difficulty rating: 2800
Tags: constructive algorithms, dfs and similar, trees

The new pedestrian zone in Moscow city center consists of $$$n$$$ squares connected with each other by $$$n - 1$$$ footpaths. We define a simple path as a sequence of squares such that no square appears in this sequence twice and any two adjacent squares in this sequence are directly connected with a footpath. The size of a simple path is the number of squares in it. The footpaths are designed in a such a way that there is exactly one simple path between any pair of different squares.

During preparations for Moscow City Day the city council decided to renew ground tiles on all $$$n$$$ squares. There are $$$k$$$ tile types of different colors, numbered from $$$1$$$ to $$$k$$$. For each square exactly one tile type must be selected and then used to cover this square surface. To make walking through the city center more fascinating, it was decided to select tiles types for each square in such a way that any possible simple path of size exactly $$$k$$$ contains squares with all $$$k$$$ possible tile colors.

You need to find out whether it is possible to place the tiles this way or not.

Input format:
The first line contains two integers $$$n$$$, $$$k$$$ ($$$2 \le k \le n \le 200\,000$$$) — the number of squares in the new pedestrian zone, the number of different tile colors.

Each of the following $$$n - 1$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — numbers of the squares connected by the corresponding road.

It's guaranteed, that it's possible to go from any square to any other square, moreover there is exactly one such simple path.

Output format:
Print "Yes" if it is possible to assign tile colors this way and "No" otherwise.

In case your answer is "Yes", print $$$n$$$ integers from $$$1$$$ to $$$k$$$ each, the color of the tile for every square.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
The following pictures illustrate the pedestrian zone in first and second examples. The second picture also shows one possible distribution of colors among the squares for $$$k = 4$$$.

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

Example output:
Yes
1 1 2 3 4 1 1

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

Example output:
No

Editorial:
Suppose there exists a vertex with tree with a tree paths going from it, with longest paths of lengths $$$a$$$, $$$b$$$ and $$$c$$$ (in edges).
Then if $$$a + b \ge k - 1$$$, $$$b + c \ge k - 1$$$, $$$a + c \ge k - 1$$$, then clearly the answer is Impossible.
We can check whether such vertex exists in $$$\mathcal{O}(n)$$$ using subtree dp and "uptree dp".
Good news: this is the only case when the answer is "No".
Bad news: providing the coloring is slightly more sophisticated.
In fact, we can prove that the following coloring works:
• Construct a tree's diameter.
• Color vertices on diameter with periodic colors: $$$1$$$, $$$2$$$, ..., $$$k$$$, $$$1$$$, $$$2$$$, ...
• By the way, if diameter has less than $$$k$$$ vertices, any coloring will be correct.
• Cut the diameter in half, the parts' lengths will differ by $$$1$$$ atmost.
• Color both halves of the tree with dfs: colors in the left part will decrease $$$i \to i - 1 \to \ldots$$$, while colors in the right part will increase $$$i \to i + 1 \to \ldots$$$.
• The result will look roughly as follows:
The total complexity is $$$\mathcal{O}(n)$$$.
Let's give a sketch of the proof why this coloring works. Well, suppose there is some bad path of $$$k$$$ vertices. Let's analyze path's position with respect to the diameter.
Case 1. The bad path is not related to the diameter.
It's easy to see that blue part of diameter is greater or equal than any half of the red path; so the vertex $$$v$$$ is a bad vertex to the our criterion.
Case 2. The bad path goes through a diameter, but lies in one half of it.
The vertex $$$v$$$ makes a bad vertex for the criterion, just for the same reasons.
Case 3. The bad path goes through a diameter, and lies in both halves.
If you recall how our coloring looks like, you will see that all paths of this form are well-colored.