给你两个简单的无向图 $$$F$$$ 和 $$$G$$$ 以及 $$$n$$$ 顶点。 $$$F$$$ 具有 $$$m_1$$$ 边,而 $$$G$$$ 具有 $$$m_2$$$ 边。您可以多次执行以下两种类型的操作之一:
- 选择两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u,v \leq n$$$),使得 $$$F$$$ 中的 $$$u$$$ 和 $$$v$$$ 之间有一条边。然后,从 $$$F$$$ 中删除该边。
- 选择两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u,v \leq n$$$),使得 $$$F$$$ 中的 $$$u$$$ 和 $$$v$$$ 之间没有边。然后,在 $$$F$$$ 中的 $$$u$$$ 和 $$$v$$$ 之间添加一条边。
确定所需的最小操作数,使得对于所有整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u,v \leq n$$$),$$$F$$$ 中存在从 $$$u$$$ 到 $$$v$$$ 的路径当且仅当存在从 $$$u$$$ 到 $$$v$$$ 的路径$$$G$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 独立测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m_1$$$ 和 $$$m_2$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$, $$$0 \leq m_1,m_2 \leq 2\cdot 10^5$$$) — 顶点数, $$$F$$$ 中的边数,以及 $$$G$$$ 中的边数。
以下 $$$m_1$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v\leq n$$$) — $$$F$$$ 中的 $$$u$$$ 和 $$$v$$$ 之间有一条边。保证不存在重复边或自环。
以下 $$$m_2$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u,v\leq n$$$) — $$$G$$$ 中的 $$$u$$$ 和 $$$v$$$ 之间有一条边。保证不存在重复边或自环。
保证所有测试用例的$$$n$$$总和、$$$m_1$$$总和、$$$m_2$$$总和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,表示新行所需的最少操作。
示例
输入 #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
输出 #1
3 0 2 0 2
注意
在第一个测试用例中您可以执行以下三个操作:
1. 在顶点 $$$1$$$ 和顶点 $$$3$$$ 之间添加一条边。
2. 删除顶点$$$1$$$ 和顶点$$$2$$$ 之间的边。
3. 删除顶点$$$2$$$ 和顶点$$$3$$$ 之间的边。
在第二个测试用例中,$$$F$$$ 和 $$$G$$$ 已经满足一开始的条件。
在第五个测试用例中,从 $$$1$$$ 到 $$$3$$$ 以及从 $$$2$$$ 到 $$$3$$$ 的边都必须被删除。