题目描述

给定两个具有 $n$ 个顶点的简单无向图 $F$ 和 $G$。其中 $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$（$1 \leq u, v \leq n$），$F$ 中存在从 $u$ 到 $v$ 的路径当且仅当 $G$ 中存在从 $u$ 到 $v$ 的路径。

输入格式

第一行包含一个整数 $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$ 中的一条边。保证没有重复边或自环。

接下来的 $m_2$ 行每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$）—— 表示 $G$ 中的一条边。保证没有重复边或自环。

保证所有测试用例的 $n$ 之和、$m_1$ 之和以及 $m_2$ 之和均不超过 $2 \cdot 10^5$。

输出格式

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

说明/提示

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

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

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

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

翻译由 DeepSeek R1 完成

样例

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