#P17735. 回忆

回忆

题目描述

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

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

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

如果在某一轮回忆中,他们同时回忆到了问题 sis_i 和问题 tit_i,则称第 ii 次研究被想起。

为了更好地理解上述概念,考察以下例子:n=5n=5,问题 11 与问题 2,32,3 相关,问题 33 与问题 4,54,5 相关。一轮可能的回忆是:从问题 22 开始回忆,切换思绪到问题 11,再切换到问题 33,最终切换到问题 55 并结束回忆。如果 m=4m=4,(s1,t1)=(1,2)(s_1,t_1)=(1,2),(s2,t2)=(1,4)(s_2,t_2)=(1,4),(s3,t3)=(s4,t4)=(3,5)(s_3,t_3)=(s_4,t_4)=(3,5),那么这轮回忆会让第 11 次、第 33 次和第 44 次研究被想起,而第 22 次研究不会被想起。

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

输入格式

输入的第一行包含一个正整数 TT,表示数据组数。

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

接下来 n−1n-1 行每行包含两个正整数 ui,viu_i,v_i,表示问题 uiu_i 与问题 viv_i 相关。

接下来 mm 行每行包含两个正整数 si,tis_i,t_i,描述一次研究。

输出格式

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

样例输入

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

样例解释

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

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

第二轮回忆中,从问题 44 开始,依次切换思绪到问题 3,13,1。此时第 2,52,5 次研究被想起。

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

测试点约束

对于所有的测试点:

  • 1≤n,m≤2×1051\le n,m\le 2\times 10^5;
  • 1≤∑n,∑m≤5×1051\le \sum n,\sum m\le 5\times 10^5;
  • 1≤ui,vi,si,ti≤n1\le u_i,v_i,s_i,t_i\le n,si≠tis_i\ne t_i;
  • 保证输入的 (ui,vi)(u_i,v_i) 构成一棵树,sis_i 在以 11 为根的树上是 tit_i 的祖先。
测试点编号 限制 特殊性质
1∼41\sim 4 T≤3000, n≤50, m≤15T\le 3000,\ n\le 50,\ m\le 15,且最多有 55 组数据满足 m≥10m\ge 10 无
5∼65\sim 6 n,m≤100n,m\le 100,∑n3,∑m3≤3×107\sum n^3,\sum m^3\le 3\times10^7 A
77 同上 B
88 C
99 无
10∼1110\sim 11 n,m≤1000n,m\le 1000,∑n2,∑m2≤3×107\sum n^2,\sum m^2\le 3\times10^7 A
1212 同上 B
1313 C
14∼1614\sim 16 无
17∼1817\sim 18 n,m≤2×105n,m\le 2\times10^5,∑n,∑m≤5×105\sum n,\sum m\le5\times10^5 B
19∼2019\sim 20 同上 C
21∼2321\sim 23 A
24∼2524\sim 25 无

特殊性质 A: 保证 nn 为偶数,且树的结构为:对于任意正整数 1≤i≤⌊n/2⌋1\le i\le\lfloor n/2\rfloor,2i2i 的父亲为 2i−12i-1;若 i≥2i\ge2,则 2i−12i-1 的父亲为 2i−32i-3。

特殊性质 B: 保证对于所有的正整数 1≤i≤m1\le i\le m,sis_i 为 tit_i 的父亲。

特殊性质 C: 保证对于所有的正整数 1≤i≤m1\le i\le m,si=1s_i=1。

对于每一组测试点,如果你的输出格式正确,且每一组数据输出的答案正确,那么你会获得 44 分。

否则,如果你的输出格式正确,且对于每一组数据,你输出的答案与正确答案相等或者比正确答案大 11,那么你将在此测试点上获得 33 分。

请注意,为了取得部分分,你必须保证输出格式正确,即:输出恰好有 mm 行,且每行是一个正整数。

此外,如果某组测试数据中你输出的结果比答案小 11 而不是大 11,那么你不能在该测试点获得 33 分。

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