P9520 [JOIST 2022] Prison / Jail

JOIST 2022 D1T1.

In the JOI Kingdom, the place with the strictest security is the IOI Prison. There are $N$ rooms in the IOI Prison, numbered $1,\dots,N$. There are $N-1$ corridors. The $i$-th corridor $(1\le i\le N-1)$ connects rooms $A_i$ and $B_i$ in both directions. Any two rooms are reachable from each other. There are $M$ prisoners in the IOI Prison, numbered $1,\dots,M$. The bedroom and workshop of the $j$-th prisoner $(1\le j\le M)$ are rooms $S_j,T_j$, respectively. A prisoner may work in another prisoner's bedroom. However, each room can be the bedroom of at most one prisoner, and the workshop of at most one prisoner. One morning, these $M$ prisoners need to move from their bedrooms to their workshops. Warden Mr. APIO must instruct the prisoners to move in the following way: - **Instruction**: Choose a prisoner, then order him to move from his current room to a room that is directly connected to it by an edge. To avoid communication between prisoners, it is not allowed to move a prisoner into a room where another prisoner is present. To start work as early as possible, Mr. APIO wants to know whether there exists a plan consisting of any number of instructions such that every prisoner can reach his workshop from his bedroom along a **shortest path**. Write a program that, given all the information about the rooms, corridors, and prisoners as described above, determines whether such a plan exists.

Each testdata contains multiple test cases. The first line contains an integer $Q$, indicating that this testdata contains $Q$ test cases. For each test case: The first line contains an integer $N$, the number of rooms. The next $N-1$ lines each contain two integers $A_i,B_i$, describing a corridor connecting the two rooms. The next line contains an integer $M$, the number of prisoners. The next $M$ lines each contain two integers $S_i,T_i$, the bedroom and workshop of a prisoner.

Output $Q$ lines. On the $i$-th line, for the $i$-th test case, output `Yes` if there exists a plan that satisfies the requirements, otherwise output `No`.

**[Sample Explanation #1]** The task can be completed by issuing the following instructions: 1. Let prisoner $2$ move from room $4$ to room $5$. 2. Let prisoner $1$ move from room $3$ to room $4$. 3. Let prisoner $2$ move from room $5$ to room $6$. 4. Let prisoner $2$ move from room $6$ to room $7$. 5. Let prisoner $2$ move from room $7$ to room $8$. This sample satisfies the constraints of all subtasks. **[Sample Explanation #2]** This sample satisfies the constraints of subtasks $1,3,4,5,6,7$. **[Constraints]** For all data, it holds that: - $1\leq Q\leq 1000$. - $1\leq N\leq 120000$. - $1\leq A_i\lt B_i\leq N$ $(i\in [1,N-1])$. - $2\leq M\leq N$. - $1\leq S_i,T_i\leq N$ $(i\in [1,M])$. - $S_i$ $(i\in[1,M])$ are pairwise distinct. - $T_i$ $(i\in[1,M])$ are pairwise distinct. - $S_j \ne T_j$ $(j\in [1, M])$. - Any two rooms are mutually reachable via the given roads. - Over all test cases, the sum of $N$ does not exceed $120000$. The additional constraints and scores for each subtask are given in the table below: |Subtask ID|Additional Constraints|Score| |:-:|:-:|:-:| |$1$|$A_i=i,B_i=i+1~(i\in[1,N-1])$|$5$| |$2$|$Q\leq 20, N\leq 250, M=2$|$5$| |$3$|$Q\leq 20, N\leq 250, M\leq 6$|$16$| |$4$|$Q\leq 20, N\leq 250, M\leq 100$|$28$| |$5$|$Q\leq 20, M\leq 500$|$12$| |$6$|Any two rooms can be reached via at most $20$ roads.|$11$| |$7$|No additional constraints.|$23$| Translated by ChatGPT 5