← 返回题目列表

Codeforces · 2060/E

E. 图形构成

中文机器翻译题面 查看原题

给你两个简单的无向图 $$$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$$$ 的边都必须被删除。