「AHOI2022」回忆

题目描述

少年时，他们提出了 $n$ 个问题，从 $1$ 到 $n$ 编号。一个问题总由一个更基础的问题衍生而来，因此问题之间构成了一个树形的结构：$1$ 号问题是最基本的问题，也就是树的根节点，而其他问题都由其父亲节点对应的问题衍生而来。如果两个问题在树上相邻，则称这两个问题彼此相关。

少年时期的他们一共做了 $m$ 次研究，第 $i$ 次的研究从提出较为基本的问题 $s_i$ 开始，将它不断地修改、推广，最终提出问题 $t_i$。这些研究满足 $s_i \ne t_i$ 且 $s_i$ 必定是 $t_i$ 的祖先。即使研究的问题完全相同，从不同的角度研究会有不同的结果，因此可能存在 $i \ne j, (s_i, t_i) = (s_j, t_j)$ 的情形。

现在，他们正一轮轮地回忆着少年时提出的问题。在他们每一轮对问题的回忆中，他们首先回忆到 $n$ 个问题中的任意一个。接下来，如果存在与当前回忆到的问题彼此相关且在这轮回忆中没有被回忆到的问题，那么他们可以将思绪从当前问题上切换到这些问题中的任意一个，并回忆到这个新的问题。他们可以不断地切换思绪，也可以在回忆到任何一个问题之后结束回忆。每一轮回忆是独立的，也就是说一个问题可以被多轮回忆回忆起。

如果在某一轮回忆中，他们同时回忆到了问题 $s_i$ 和问题 $t_i$，则称第 $i$ 次研究被想起。

他们问你们的最后一个问题是：如果每轮回忆的起点以及思绪的切换可以任意选择，最少需要多少轮回忆才能使所有的研究都被想起。

输入格式

本题有多组测试数据。输入的第一行包含一个正整数 $T$，表示数据组数。

对于每组测试数据，第一行包含两个正整数 $n, m$，分别表示问题的个数和研究的个数。

接下来 $n - 1$ 行每行包含两个正整数 $u_i, v_i$，表示问题 $u_i$ 与问题 $v_i$ 相关。

接下来 $m$ 行每行包含两个正整数 $s_i, t_i$，描述一次研究。

输出格式

对于每组测试数据输出一行一个正整数，表示他们最少需要回忆的轮数使得 $m$ 次研究均被想起。

样例 1

输入

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

输出

2
2

样例中的第一组数据与题目描述所给的例子相同。一种可能的回忆方案为：

• 第一轮回忆中，从问题 $2$ 开始，依次切换思绪到问题 $1, 3, 5$。此时第 $1, 3, 4$ 次研究被想起，但第 $2, 5$ 次没有。
• 第二轮回忆中，从问题 $4$ 开始，依次切换思绪到问题 $3, 1$。此时第 $2, 5$ 次研究被想起。

第二组数据符合特性 A 的要求。一种可能的回忆方案为：第一次回忆依次回忆到 $2, 1, 3, 5, 6$，第二次回忆依次回忆到 $8, 7, 9, 10$。

样例 2

见附加文件下的 memory2.in 与 memory2.ans。

这组数据满足了测试点 $1 \sim 4$ 的条件。

样例 3

见附加文件下的 memory3.in 与 memory3.ans。

这组样例满足了特性 A 的条件。且除了后 $3$ 组数据外，其余样例均满足 $n, m \le 1000$。除了后 $30$ 组数据外，其余样例均满足 $n, m \le 30$。你也可以用这组样例完成对较小规模数据的测试。

样例 4

见附加文件下的 memory4.in 与 memory4.ans。

这组样例满足了测试点 $24 \sim 25$ 的条件。同样例 #3，本样例满足：除了后 $3$ 组数据外，其余样例均满足 $n, m \le 1000$。除了后 $30$ 组数据外，其余样例均满足 $n, m \le 30$。你也可以用这组样例完成对较小规模数据的测试。

样例 5

见附加文件下的 memory5.in 与 memory5.ans。

这组样例满足了特性 B 的条件。

样例 6

见附加文件下的 memory6.in 与 memory6.ans。

这组样例满足了特性 C 的条件。

数据范围与提示

本题共 $25$ 个测试点。对于所有的测试点，$1 \le n, m \le 2 \times 10^5$，$1 \le \sum n, \sum m \le 5 \times 10^5$，$1 \le u_i, v_i, s_i, t_i \le n$，$s_i \ne t_i$。保证输入的 $(u_i, v_i)$ 构成一棵树，$s_i$ 在以 $1$ 为根的树上是 $t_i$ 的祖先。

测试点	规模限制	特殊性质
1 ~ 4	$T \le 3000$，$n \le 50$，$m \le 15$ 且最多有 $5$ 组数据满足 $m \ge 10$	无
5 ~ 6	$n, m \le 100$，$\sum n^3, \sum m^3 \le 3 \times 10^7$	A
7		B
8		C
9		无
10 ~ 11	$n, m \le 1000$，$\sum n^2, \sum m^2 \le 3 \times 10^7$	A
12		B
13		C
14 ~ 16		无
17 ~ 18	$n, m \le 2 \times 10^5$，$\sum n, \sum m \le 5 \times 10^5$	B
19 ~ 20		C
21 ~ 23		A
24 ~ 25		无

特殊性质 A：保证 $n$ 为偶数，且树的结构为：对于任意正整数 $1 \le i \le \lfloor \frac{n}{2} \rfloor$，$2i$ 的父亲为 $2i - 1$；若 $i \ge 2$，则 $2i - 1$ 的父亲为 $2i - 3$。

特殊性质 B：保证对于所有的正整数 $1 \le i \le m$，$s_i$ 为 $t_i$ 的父亲。

特殊性质 C：保证对于所有的正整数 $1 \le i \le m$，$s_i = 1$。

请注意，测试点的难度与编号并没有直接关系。

本题部分测试点读入量较大。为了优化程序的总运行时间，我们建议你采用较为快速的读入方式。