logo AlgoBeat OnlineJudge
登录 注册

#104042. [BZOJ 4042] [Cerc2014] parades

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

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

输入格式

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

每个测试用例的第一行包含一个整数:结点数 。 接下来的 行中的每一行包含两个整数 ,表示端点 由街道连接。 每个交叉路口最多有 条街道。

下一行包含一个整数:计划游行的数量

接下来的 行中的每一行包含两个整数 ,这意味着游行计划从交叉点 开始,并在交叉点 处完成。 没有两个游行共享两个端点。

输出格式

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

样例

样例输入 #1

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

样例输出 #1

2

数据范围与提示

对于 的数据,