猫咪军团

Problem Description

【猫咪军团】侵略狗星！！！

狗星有 $n$ 个地区，有 $n - 1$ 条双向道路使狗星的所有地区连通。猫咪军团要投放一些猫咪到狗星的某些地区上以抓捕狗仔。猫咪们修建了 $m$ 条猫咪通道。猫咪只能走猫咪通道，狗仔只能走狗星道路。

猫咪通道

• 一条猫咪通道连接两个不同的点 $u$ 、$v$ ，并且猫咪通道上有一个中转站。
• 猫咪想从 $u$ 走到$v$ 或从 $v$ 走到 $u$ 时，需要先走到中转站，再从中转站走到另一个点。 当某只猫咪在某个中转站时，若狗星道路上也有一条边连接 $u$ 和 $v$ ，视为这只猫咪在狗星道路的这条路中间。

游戏规则

• 猫咪军团先投放猫咪，狗仔再选择初始位置。
• 猫咪和狗仔交替行动，由猫咪先手（事实上先后手不影响结果）。

猫咪行动

• 选择一只猫咪，然后让它从一个地区走到一个中转站上，或者从中转站走到一个地区上（只能走一次，经过”半条“猫咪通道）。

狗仔行动

• 狗仔可以通过狗星的道路移动到另一个地区（可以经过任意条道路和地区，只要路径中间及路径经过的地区没有猫咪），也可以原地不动。 任何时刻，只要有猫咪和狗仔在同一个地区，就视作抓捕成功。

目标

在保证能抓捕住狗仔的情况下，最小化要投放的猫咪的数量。

补充说明

1. 多只猫咪可以待在同一个地区，猫咪们和狗仔都知道彼此的位置。
2. 猫咪通道不一定将狗星的所有地区连通。

Input

第一行一个正整数 $T(1\leq T\leq 100)$，表示测试用例组数。对每组测试用例： 第一行两个正整数 $n,m(1\leq n\leq 10^5,0\leq m\leq 10^5)$ ,分别表示地区数量(点数)和猫咪通道的数量。 接下来 $n-1$行，每行两个正整数 $u,v$，表示狗星地图上的一条边。 接下来 $m$ 行，每行两个正整数 $u,v$，表示连接 $u$ 和 $v$ 的一条猫咪通道。 保证对所有测试用例，$ \sum n\leq 5\times 10^5,\sum m\leq 6.5\times 10^5 $.

Output

共 $T$ 行，每行一个整数表示至少需要投放的猫咪数量。

Sample Input

3
3 0
2 1
2 3
3 1
1 2
3 1
2 3
3 3
1 2
3 2
2 1
3 2
1 3

Sample Output

3
2
1

Hint

• 第一组数据，没有猫咪通道，所以每个地区都要投放 $1$ 只猫咪。
• 第二组数据，地区 $1$ 和 $2$，$3$ 无法通过猫咪通道连通，地区 $1$ 需要投放 $1$ 只猫咪，地区$2$ 或 $3$ 需要投放且只需要投放一只猫咪。

- 第三组数据，猫咪通道连成一个完全图，可以证明投放 $1$ 只猫咪即可。 ## Source

2024“钉耙编程”中国大学生算法设计超级联赛（5）