P13921 [PO Final 2024] 回家 / Trafikverket's Mistake

不可思议的事情发生了！交通部门制定的计划出了岔子。就在人们即将下班离开小镇隆恩雪平时，一场可怕的暴风雪导致镇上所有互联网中断。由于互联网中断，他们无法获取交通部门计划的最新信息，因此无法在不冒撞车风险的情况下开车回家。 现在你的任务是找到一种方法，让所有人都能安全回家，避免任何碰撞。隆恩雪平的道路网络由 $ 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}$。

### 子任务 **本题采用捆绑测试。** | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | 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 | 无额外约束。 |