← 返回题目列表

Codeforces · 1929/E

E. 萨沙和快乐树砍伐

中文机器翻译题面 查看原题

Sasha 获得了一棵树$$$^{\dagger}$$$,顶点为 $$$n$$$,作为赢得另一场比赛的奖励。然而,当他庆祝胜利回家后,他发现树的某些部分不见了。萨沙记得他给这棵树的一些边缘涂了颜色。他确信对于任何 $$$k$$$ 顶点对 $$$(a_1, b_1), \ldots, (a_k, b_k)$$$,他在顶点 $$$a_i$$$ 和 $$$b_i$$$ 之间的简单路径 $$$^{\ddagger}$$$ 上至少对一条边进行了着色。

Sasha 不记得他到底有多少条边着色,因此他要求你告诉他满足上述条件他可以着色的最小边数。

$$$^{\dagger}$$$树是无环的无向连通图。

$$$^{\ddagger}$$$简单路径是最多经过每个顶点一次的路径。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 树中的顶点数。

接下来的 $$$(n - 1)$$$ 行描述树的边缘。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — 由第 $$$i$$$ 条边连接的顶点数。

下一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 20$$$) — Sasha 对简单路径上至少一条边进行着色的顶点对的数量。

接下来的 $$$k$$$ 行描述对。第 $$$j$$$ 行包含两个整数 $$$a_j$$$ 和 $$$b_j$$$ ($$$1 \leq a_j, b_j \leq n, a_j \neq b_j$$$) — 第 $$$j$$$ 对中的顶点。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。保证所有测试用例的 $$$2^k$$$ 总和不超过 $$$2^{20}$$$。

输出

对于每个测试用例,输出一个整数——Sasha 可以着色的最小边数。

示例

输入 #1

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

输出 #1

1
2
4

注意

在第一个测试用例中,Sasha 可以仅对一条边 $$$(1, 2)$$$ 着色。那么,顶点 $$$1$$$ 和 $$$3$$$ 之间以及顶点 $$$4$$$ 和 $$$1$$$ 之间的简单路径上将至少存在一条彩色边。

在第二个测试用例中,Sasha 可以为边缘 $$$(1, 6)$$$ 和 $$$(1, 3)$$$ 着色。