CF1929E.Sasha and the Happy Tree Cutting

Sasha was given a tree$^{\dagger}$ with $n$ vertices as a prize for winning yet another competition. However, upon returning home after celebrating his victory, he noticed that some parts of the tree were missing. Sasha remembers that he colored some of the edges of this tree. He is certain that for any of the $k$ pairs of vertices $(a_1, b_1), \ldots, (a_k, b_k)$, he colored at least one edge on the simple path$^{\ddagger}$ between vertices $a_i$ and $b_i$.

Sasha does not remember how many edges he exactly colored, so he asks you to tell him the minimum number of edges he could have colored to satisfy the above condition.

$^{\dagger}$A tree is an undirected connected graph without cycles.

$^{\ddagger}$A simple path is a path that passes through each vertex at most once.

萨沙因赢得另一场比赛而获得了一棵含有 $n$ 个顶点的树$^{\dagger}$ 作为奖品。然而，在庆祝胜利回家后，他发现这棵树缺失了一些部分。萨沙记得他曾给该树中的一些边染过色。他确信：对于给定的 $k$ 对顶点 $(a_1, b_1), \ldots, (a_k, b_k)$ 中的任意一对 $(a_i, b_i)$，连接 $a_i$ 与 $b_i$ 的简单路径$^{\ddagger}$ 上至少有一条边被他染过色。

萨沙不记得自己确切染了多少条边，因此他请你告诉他：为满足上述条件，他最少需要染多少条边？

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

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

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 10^5$) — the number of vertices in the tree.

The next $(n - 1)$ lines describe the edges of the tree. The $i$-th line contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$) — the numbers of the vertices connected by the $i$-th edge.

The next line contains a single integer $k$ ($1 \leq k \leq 20$) — the number of pairs of vertices between which Sasha colored at least one edge on a simple path.

The next $k$ lines describe pairs. The $j$-th line contains two integers $a_j$ and $b_j$ ($1 \leq a_j, b_j \leq n, a_j \neq b_j$) — the vertices in the $j$-th pair.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. It is guaranteed that the sum of $2^k$ over all test cases does not exceed $2^{20}$.

每个测试包含多个测试用例。第一行包含一个整数 $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}$。

For each test case, output a single integer — the minimum number of edges Sasha could have colored.

对于每个测试用例，输出一个整数——Sasha 可能涂色的最少边数。

In the first test case, Sasha could have colored only one edge $(1, 2)$. Then, there would be at least one colored edge on the simple path between vertices $1$ and $3$, and vertices $4$ and $1$.

In the second test case, Sasha could have colored the edges $(1, 6)$ and $(1, 3)$.

在第一个测试用例中，萨沙本可以只给边 $(1, 2)$ 染色。此时，在顶点 $1$ 与 $3$ 之间的简单路径上，以及顶点 $4$ 与 $1$ 之间的简单路径上，均至少存在一条被染色的边。

在第二个测试用例中，萨沙可以给边 $(1, 6)$ 和 $(1, 3)$ 染色。