P4757 [CERC2014] Parades

在永恒节日之城，有 $n$ 个街道交叉口和 $n-1$ 条双向街道，每条街道连接两个交叉口。每两个交叉口之间，恰好有一条（直接或间接）路径连接它们。没有交叉口是超过 10 条街道的端点。 每年 9 月 13 日（即一年中的第 256 天），永恒节日之城会举行许多庆祝活动。特别是，市民们想要组织 $m$ 场游行。第 $i$ 场游行从交叉口 $u_i$ 开始，到交叉口 $v_i$ 结束，沿着端点之间的唯一路径进行。 作为城市的市长，你负责市民的安全。因此，你规定任何两场游行都不允许使用相同的街道，尽管它们可以有共同的交叉口，甚至是共同的端点。 为了安抚市民，尽量组织尽可能多的游行，同时不违反安全规定。

输入的第一行包含测试用例的数量 $T$。接下来的每个测试用例描述如下： 每个测试用例的第一行包含一个整数：交叉口的数量 $n(2 \le n \le 1000)$。接下来的 $n - 1$ 行中的每一行包含两个整数 $a, b(1 \le a eq b \le n)$，表示交叉口 $a$ 和 $b$ 由一条街道连接。每个交叉口最多有 10 条街道离开。 下一行包含一个整数：计划的游行数量 $m, 0 \le m \le \binom{n}{2}$。 接下来的 $m$ 行中的每一行包含两个整数 $u_i, v_i (1 \le u_i eq v_i \le n)$，表示计划从交叉口 $u_i$ 开始，并在交叉口 $v_i$ 结束的游行。没有两场游行共享两个端点。

对于每个测试用例，输出一行，包含在不超过一条街道被多场游行使用的情况下可以组织的最大游行数量。

题面翻译由 ChatGPT-4o 提供。