题目背景

JOISC2022 D1T1

题目描述

在 JOI 王国，安保最严格的地方就是 IOI 监狱。IOI 监狱中有 $N$ 个房间，以 $1,\dots,N$ 编号。其中有 $N-1$ 条通道。第 $i$ $(1\le i\le N-1)$ 条通道双向地连接房间 $A_i$ 和 $B_i$。任意两个房间都可以相互到达。

IOI 监狱中有 $M$ 个囚犯，以 $1,\dots,M$ 编号。第 $j$ $(1\le j\le M)$ 个囚犯的卧室和工作室分别是房间 $S_j,T_j$。一个囚犯可能在另一个囚犯的卧室工作。然而，每个房间最多成为一个囚犯的卧室，一个囚犯的工作室。

一天早上，这 $M$ 个囚犯需要从他们的卧室移动到他们的工作室。典狱长 APIO 先生需要按如下方式指示囚犯移动：

• 指令：选择一个囚犯，然后命令他从当前所在的房间移动到一个与该房间有直接连边的房间。为了避免囚犯交流，不允许将囚犯移动到有其他囚犯在的房间。

为了尽早开始工作，APIO 先生想知道，是否存在一种给出任意条指令的方案使得每个囚犯以最短路径从卧室到达工作室。

请编写一个程序，在给定如上房间、通道和罪犯的所有信息后判断是否存在满足条件的方案。

输入格式

每个测试数据包含多组测试用例。

第一行一个整数 $Q$，表示这个测试数据包含 $Q$ 组测试用例。

对于每组测试用例：

第一行一个整数 $N$，表示房间个数。

接下来 $N-1$ 行每行两个整数 $A_i,B_i$ 表示通道连接房间的编号。

接下来一行一个整数 $M$ 表示囚犯个数。

接下来 $M$ 行，每行两个整数 $S_i,T_i$ 表示囚犯的卧室和工作室。

输出格式

输出 $Q$ 行，第 $i$ 行表示对于第 $i$ 组测试用例，如果存在一种满足题意的方案，输出 Yes，否则输出 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

提示

【样例解释 #1】

可以通过发送如下指令完成任务：

1. 让囚犯 $2$ 从 $4$ 号房间移动到 $5$ 号房间。
2. 让囚犯 $1$ 从 $3$ 号房间移动到 $4$ 号房间。
3. 让囚犯 $2$ 从 $5$ 号房间移动到 $6$ 号房间。
4. 让囚犯 $2$ 从 $6$ 号房间移动到 $7$ 号房间。
5. 让囚犯 $2$ 从 $7$ 号房间移动到 $8$ 号房间。

这组样例满足所有子任务的限制。

【样例解释 #2】

这组样例满足子任务 $1,3,4,5,6,7$ 的限制。

【数据范围】

对于所有数据，满足：

• $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])$ 互不相同。
• $T_i$ $(i\in[1,M])$ 互不相同。
• $S_j \ne T_j$ $(j\in [1, M])$。
• 任意两个房间之间可以通过给定道路互相到达。
• 对于所有测试用例，$N$ 的总和不超过 $120000$。

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
$1$	$A_i=i,B_i=i+1~(i\in[1,N-1])$	$5$
$2$	$Q\leq 20, N\leq 250, M=2$
$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$	任意两个房间之间都可以通过不超过 $20$ 条道路到达。	$11$
$7$	无附加限制	$23$