Background

JOIST 2022 D1T1.

Problem Description

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.

Input Format

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 Format

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.

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

Yes

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

Yes
No

Hint

[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:

Translated by ChatGPT 5