题目描述

不可思议的事情发生了！交通部门制定的计划出了岔子。就在人们即将下班离开小镇隆恩雪平时，一场可怕的暴风雪导致镇上所有互联网中断。由于互联网中断，他们无法获取交通部门计划的最新信息，因此无法在不冒撞车风险的情况下开车回家。

现在你的任务是找到一种方法，让所有人都能安全回家，避免任何碰撞。隆恩雪平的道路网络由 $N$ 座房屋和 $N - 1$ 条道路组成。每条道路直接连接两座房屋。如果你在某座房屋，可以通过道路前往与当前房屋相连的所有房屋。该网络还被构建成，可以通过一条或多条道路在任意两座房屋之间通行。

多亏了交通部门计划制定前的数据收集，你清楚每个人身在何处（他们都在工作，你知道他们的工作地点），以及他们想回哪个家。现在，每个人都坐在工作地点外的车里，挡住了其他车辆通过该房屋的道路。为了让所有人安全回家，你将使用一架无人机，它会飞来飞去，告诉人们“开车回家”。他们会沿着工作地点和家之间最短的路径开车回家，中途不停。一旦到家，他们会将车停入车库，不再阻碍任何道路。由于天气寒冷，无人机速度非常慢，你可以假设每个人都有足够的时间开车回家并停车，然后无人机才会到达下一个人那里。

如果一辆车开始回家，而路上有另一辆车挡道，由于路面湿滑，它们会发生碰撞。判断是否存在一个让所有汽车都能完全避免碰撞地开回家的顺序。如果存在，请找出它。

输入格式

输入的第一行包含两个整数 $N$ 和 $C$ ($1 \le C \le N \le 2 \cdot 10^5$)，分别表示隆恩雪平道路网络中的房屋数量和想要回家的人数。

接下来 $N - 1$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le N, a \neq b$)，表示房屋 $a$ 和房屋 $b$ 之间有一条道路。保证可以通过一条或多条道路在任意两座房屋之间通行。

之后有 $C$ 行，每行包含两个整数 $W_i$ 和 $H_i$ ($1 \le W_i, H_i \le N$)，分别表示第 $i$ 个人工作所在的房屋和他们居住的房屋。保证每座房屋最多只有一个人出发（对于任意 $1 \le i, j \le N, i \neq j$，都有 $W_i \neq W_j$）。

输出格式

如果存在一个居民可以无碰撞地开车回家的顺序，则首先输出 $\texttt{Yes}$。然后，打印出居民应该回家的顺序。输入中第一个居民对应顺序中的 1，第二个对应 2，依此类推。

如果不存在无碰撞的顺序，则输出 $\texttt{No}$。

5 4
1 2
2 3
2 4
4 5
5 3
4 3
3 2
1 3

Yes
3 4 2 1

4 2
1 2
2 3
3 4
2 4
3 1

No

提示

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | 1 | 5 | $C \le 8, N \le 100$ | | 2 | 10 | $N \le 100$ | | 3 | 10 | $N \le 4000$，最长路径的长度小于 50。 | | 4 | 25 | $N \le 4000$ | | 5 | 50 | 无额外约束。 |