루미 알고리즘

#1581플래티넘Trafikverket's Mistake

PO 2024 결선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

The unthinkable has happened! The plan laid by the traffic department (Trafikverket (See https://open.kattis.com/problems/trafikverketsplan)) has gone awry. Just before people were about to leave work in the small town of Lönnköping, a horrendous snowstorm knocked out all the internet in the town. Since the internet is down, they can't get the latest information about Trafikverket's Plan, and therefore can't drive home without risking a crash.

It is now your job to find a way for everyone to get home without any collisions. Lönnköping's road network consists of N houses and N-1 roads. Each road directly connects two houses. If you are at a certain house, you can travel to all houses connected to your current house by a road. The network is also constructed such that one can travel between every pair of houses by using one or more roads.

Thanks to the data collection that took place before the creation of Trafikverket's Plan, you know where each person is located (they are all at work, and you know where they work) and which house they want to go home to. Right now, each person is sitting in their car outside their workplace, blocking other cars from passing by that house. To get everyone home safely, you will use a drone that flies around and tells people to “drive home”. They will then drive home along the shortest path between their workplace and their home without stopping. Once they are home, they will park their car in their garage and no longer block any roads. Due to the cold, the drone is so slow that you can assume that each person has sufficient time to drive home and park before the drone reaches the next person.

If a car ever starts driving home and there is another car in the way, they will collide due to the slippery road conditions. Determine if there is an order in which the cars can drive home that is completely free from collisions. If such an order exists, find it.

Input

The first line of the input contains two integers, N and C (1 ≤ C ≤ N ≤ 2 · 10^5), the number of houses in Lönnköping's road network and the number of people who want to go home.

The following N-1 lines each contain two integers, a and b (1 ≤ a,b ≤ N, a ≠ b), indicating that there is a road between house a and house b. It is guaranteed that one can travel between every pair of houses by traveling along one or more roads.

After that, there are C lines, each containing two integers W_i and H_i (1 ≤ W_i,H_i ≤ N), indicating the house where the i-th person works and the house where they live, respectively. It is guaranteed that at most one person starts at each house (W_i ≠ W_j for every 1 ≤ i, j ≤ N, i ≠ j).

Output

If there is an order in which the residents can drive home without collisions, first output ‘‘Yes''. Then, print out the order in which the residents should drive home. The resident represented first in the input corresponds to 1 in the order, the second one to 2, and so on.

If there is no order without collisions, output ‘‘No''.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
15C ≤ 8, N ≤ 100
210N ≤ 100
310N ≤ 4000, the length of the longest path is less than 50.
425N ≤ 4000
550No additional constraints.

예제

예제 1

입력
5 4
1 2
2 3
2 4
4 5
5 3
4 3
3 2
1 3
출력
Yes
3 4 2 1 

예제 2

입력
4 2
1 2
2 3
3 4
2 4
3 1
출력
No

출처 표기

출처: Programmeringsolympiaden 2024년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.