给定两个具有 个顶点的简单无向图 和 。其中 有 条边， 有 条边。你可以执行任意次数的以下两种操作之一： 选择两个整数 和 （），使得 中存在 和 之间的边，然后将该边从 中移除。 选择两个整数 和 （），使得 中不存在 和 之间的边，然后在 中添加这条边。 求使得以下条件成立所需的最小操作次数：对于所有整数 和 （）， 中存在从 到 的路径当且仅当 中存在从 到 的路径。
输入描述:
第一行包含一个整数 （）—— 独立测试用例的数量。每个测试用例的第一行包含三个整数 、 和 （，）—— 顶点数、图  的边数和图  的边数。接下来的  行每行包含两个整数  和 （）—— 表示  中的一条边。保证没有重复边或自环。接下来的  行每行包含两个整数  和 （）—— 表示  中的一条边。保证没有重复边或自环。保证所有测试用例的  之和、 之和以及  之和均不超过 。


输出描述:
对于每个测试用例，在新的一行输出一个整数表示所需的最小操作次数。
示例1

输入

5
3 2 1
1 2
2 3
1 3
2 1 1
1 2
1 2
3 2 0
3 2
1 2
1 0 0
3 3 1
1 2
1 3
2 3
1 2

输出

3
0
2
0
2

说明

在第一个测试用例中，可以执行以下三个操作：

1. 在顶点 1 和顶点 3 之间添加一条边。
2. 移除顶点 1 和顶点 2 之间的边。
3. 移除顶点 2 和顶点 3 之间的边。

可以证明无法用更少的操作达成目标。在第二个测试用例中，初始时 F 和 G 已经满足条件。

在第五个测试用例中，必须同时移除从 1 到 3 和从 2 到 3 的两条边。
加载中...