CF1214H.Tiles Placement

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.

莫斯科市中心新建的步行区由 $n$ 个广场组成，这些广场通过 $n - 1$ 条人行小径相互连接。我们定义简单路径为一个广场序列，其中任意广场在该序列中至多出现一次，且序列中任意两个相邻广场之间均直接由一条人行小径相连。一条简单路径的大小即为其所包含的广场数量。这些人行小径的布局方式保证了：对任意两个不同的广场，其间恰好存在唯一一条简单路径。

在莫斯科市日庆典筹备期间，市政委员会决定更新全部 $n$ 个广场的地砖。共有 $k$ 种不同颜色的地砖类型，编号从 $1$ 到 $k$。每个广场必须且仅能选择一种地砖类型，并用其完全覆盖该广场表面。为了使穿行于市中心的过程更具趣味性，决定以如下方式为各广场分配地砖类型：任意一条大小恰好为 $k$ 的简单路径，都必须包含全部 $k$ 种颜色的地砖。

你需要判断：是否存在满足上述条件的地砖铺设方案。

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.

第一行包含两个整数 $n$ 和 $k$（$2 \le k \le n \le 200\,000$）—— 分别表示新步行区中的方格数量以及不同地砖颜色的数量。

接下来的 $n - 1$ 行中，每行包含两个整数 $v_i$ 和 $u_i$（$1 \le v_i, u_i \le n$）—— 表示由对应道路连接的两个方格的编号。

保证任意两个方格之间均可达，且两点间存在唯一一条简单路径。

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.

如果可以按此方式为瓷砖分配颜色，则输出“Yes”，否则输出“No”。

如果答案为“Yes”，则输出 $n$ 个整数，每个整数均在 $1$ 到 $k$ 之间，分别表示每个方格上瓷砖的颜色。

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$.

以下图片展示了前两个示例中的行人专用区。第二张图片还展示了当 $k = 4$ 时，方格间一种可能的颜色分布方式。