Score: $700$ points

问题陈述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。树中的第 $i$ 条边双向连接了顶点 $u_i$ 和 $v_i$。

对于一个排列 $P=(P_1,\ldots,P_N)$，我们定义 $f(P)$ 如下：

• 对于每个顶点 $i\ (1\leq i\leq N)$，设 $(v_1=1,v_2,\ldots,v_k=i)$ 是从顶点 $1$ 到顶点 $i$ 的简单路径，设 $L_i$ 是 $(P_{v_1},P_{v_2},\ldots,P_{v_k})$ 的最长递增子序列的长度。我们定义 $f(P) = \sum_{i=1}^N L_i$。

给定一个整数 $K$。确定是否存在一个排列 $P$ 使得 $f(P)=K$。如果存在，请展示这样一个排列。

什么是最长递增子序列？一个序列的子序列是通过从原始序列中移除零个或多个元素，并连接剩余元素而不改变顺序得到的序列。例如，$(10,30)$ 是 $(10,20,30)$ 的一个子序列，但 $(20,10)$ 不是。 一个序列的最长递增子序列是该序列中最长的严格递增子序列。什么是简单路径？对于图 $G$ 中的顶点 $X$ 和 $Y$，从顶点 $X$ 到顶点 $Y$ 的路径是一系列顶点 $(v_1,v_2, \ldots, v_k)$，使得 $v_1=X$，$v_k=Y$，并且对于所有 $1\leq i\leq k-1$，$v_i$ 和 $v_{i+1}$ 由一条边连接。此外，如果 $v_1,v_2, \ldots, v_k$ 都是不同的，它被称为从顶点 $X$ 到顶点 $Y$ 的简单路径（或简称路径）。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge of the tree connects vertices $u_i$ and $v_i$ bidirectionally.

For a permutation $P=(P_1,\ldots,P_N)$ of $(1,\ldots,N)$, we define $f(P)$ as follows:

• For each vertex $i\ (1\leq i\leq N)$, let $(v_1=1,v_2,\ldots,v_k=i)$ be the simple path from vertex $1$ to vertex $i$, and let $L_i$ be the length of a longest increasing subsequence of $(P_{v_1},P_{v_2},\ldots,P_{v_k})$. We define $f(P) = \sum_{i=1}^N L_i$.

You are given an integer $K$. Determine whether there is a permutation $P$ of $(1,\ldots,N)$ such that $f(P)=K$. If it exists, present one such permutation.

What is a longest increasing subsequence? A subsequence of a sequence is a sequence obtained by removing zero or more elements from the original sequence and concatenating the remaining elements without changing the order. For example, $(10,30)$ is a subsequence of $(10,20,30)$, but $(20,10)$ is not.
The longest increasing subsequence of a sequence is the longest strictly increasing subsequence of that sequence. What is a simple path? For vertices $X$ and $Y$ in a graph $G$, a walk from vertex $X$ to vertex $Y$ is a sequence of vertices $(v_1,v_2, \ldots, v_k)$ such that $v_1=X$, $v_k=Y$, and $v_i$ and $v_{i+1}$ are connected by an edge for all $1\leq i\leq k-1$. Furthermore, if $v_1,v_2, \ldots, v_k$ are all distinct, it is called a simple path (or simply a path) from vertex $X$ to vertex $Y$.

Constraints

• All input values are integers.
• $2 \leq N \leq 2\times 10^5$
• $1\leq K \leq 10^{11}$
• $1\leq u_i,v_i\leq N$
• The given graph is a tree.

Input

The input is given from Standard Input in the following format:

$N$ $K$

$u_1$ $v_1$

$\vdots$

$u_{N-1}$ $v_{N-1}$

Output

If there is no permutation $P$ such that $f(P)=K$, print No.

If there is a permutation $P$ such that $f(P)=K$, print it in the following format:

Yes

$P_1$ $\ldots$ $P_N$

If multiple permutations $P$ satisfy the condition, any of them will be accepted.

Sample Input 1

5 8
1 2
2 3
2 4
4 5

Sample Output 1

Yes
3 2 1 4 5

If $P=(3,2,1,4,5)$, then $f(P)$ is determined as follows:

• The simple path from vertex $1$ to vertex $1$ is $(1)$, and the length of the longest increasing subsequence of $(P_1)=(3)$ is $1$. Thus, $L_1 = 1$.

• The simple path from vertex $1$ to vertex $2$ is $(1,2)$, and the length of the longest increasing subsequence of $(P_1,P_2)=(3,2)$ is $1$. Thus, $L_2 = 1$.

• The simple path from vertex $1$ to vertex $3$ is $(1,2,3)$, and the length of the longest increasing subsequence of $(P_1,P_2,P_3)=(3,2,1)$ is $1$. Thus, $L_3 = 1$.

• The simple path from vertex $1$ to vertex $4$ is $(1,2,4)$, and the length of the longest increasing subsequence of $(P_1,P_2,P_4)=(3,2,4)$ is $2$. Thus, $L_4 = 2$.

• The simple path from vertex $1$ to vertex $5$ is $(1,2,4,5)$, and the length of the longest increasing subsequence of $(P_1,P_2,P_4,P_5)=(3,2,4,5)$ is $3$. Thus, $L_5 = 3$.

• From the above, $f(P)=1+1+1+2+3= 8$.

Hence, the permutation $P$ in the sample output satisfies the condition $f(P)=8$. Besides, $P=(3,2,4,5,1)$ also satisfies the condition, for example.

Sample Input 2

7 21
2 1
7 2
5 1
3 7
2 6
3 4

Sample Output 2

No

It can be proved that no permutation $P$ satisfies $f(P) = 21$.

Sample Input 3

8 20
3 1
3 8
7 1
7 5
3 2
6 5
4 7

Sample Output 3

Yes
2 1 3 5 6 8 4 7