题目描述

In The City of Eternal Festivities, there are $n$ street junctions and $n-1$ bidirectional streets,each street connecting two of the junctions. Between every two junctions, there is exactly one (direct or indirect) path connecting them. No junction is an endpoint for more than 10 streets.

Every 13th of September (the 256th day of the year), there are many festivities going on in The City. In particular, the citizens want to organize $m$ parades. The parade number $i$ starts at junction $u_i$ and ends at $v_i$, following the unique path between the endpoints.

As the mayor of The City, you are responsible for citizens’ safety. Therefore you decreed that no two parades are ever allowed to use the same street, though they can have common junctions,or even common endpoints.

To appease your citizens, try to organize as many parades as possible, without breaking the safety regulations.

输入格式

The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

The first line of each test case contains a single integer: the number of junctions $n(2 \le n \le 1000)$. Each of the next $n - 1$ lines contains two integers $a, b(1 \le a ≠ b \le n)$, denoting that junctions $a$ and $b$ are connected by a street. Each junction has at most $10$ streets leaving it.

The next line contains a single integer: the number of planned parades $m, 0 \le m \le (_2^n)$.

Each of the next $m$ lines contains two integers $u_i, v_i (1 \le u_i ≠ v_i \le n)$,meaning that a parade is planned to start at junction $u_i$, and finish at junction $v_i$. No two parades share both endpoints.

输出格式

For each test case, output one line containing the largest number of parades that can be organized with no street used by more than one parade.

题目大意

在永恒庆典的城市里，有N个街道路口和N-1个双向街道，每条街道连接两个路口。在每两个路口之间，正好有一条（直接或间接）连接它们的路径。没有路口是超过10条街道的终点。

九月的每第十三天（一年中的第二百五十六天），城市里会有很多庆祝活动。特别是市民要组织M游行。游行I从路口UI开始，结束于VI，是两端点之间的唯一路径。

作为城市的市长，你要对市民的安全负责。因此，你颁布法令，不允许两个游行使用同一条街，尽管它们可以有共同的连接点，甚至共同的端点。

为了安抚你的公民，在不违反安全条例的情况下，组织尽可能多的游行。

第一行输入包含测试用例T的数量。测试用例的描述如下：

每个测试用例的第一行包含一个整数：结点数n（2≤n≤1000）。 接下来的n-1行中的每一行包含两个整数a，b（1≤a≠b≤n），表示端点a和b由街道连接。 每个交叉路口最多有10条街道。

下一行包含一个整数：计划游行的数量m($0≤m≤{n\choose 2})$)。

接下来的m行中的每一行包含两个整数ui，vi（1≤ui≠vi≤n），这意味着游行计划从交叉点ui开始，并在交叉点vi处完成。 没有两个游行共享两个端点。

对于每个测试用例，输出一行包含最多数量的游行，这些游行可以被组织，不会有多个游行使用的相同的街道。

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

2