E. Составление графа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два простых неориентированных графа $$$F$$$ и $$$G$$$ с $$$n$$$ узлами. У графа $$$F$$$ есть $$$m_1$$$ рёбер, а у графа $$$G$$$ — $$$m_2$$$ рёбер. Вы можете выполнять одну из следующих двух операций любое количество раз:

  • Выберите два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u,v \leq n$$$), такие что между $$$u$$$ и $$$v$$$ в графе $$$F$$$ есть ребро. Затем удалите это ребро из $$$F$$$.
  • Выберите два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u,v \leq n$$$), такие что между $$$u$$$ и $$$v$$$ в графе $$$F$$$ нет ребра. Затем добавьте ребро между $$$u$$$ и $$$v$$$ в $$$F$$$.

Определите минимальное количество операций, необходимых для того, чтобы для всех целых чисел $$$u$$$ и $$$v$$$ ($$$1 \leq u,v \leq n$$$) существовал путь от $$$u$$$ до $$$v$$$ в $$$F$$$ если и только если существует путь от $$$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$$$) — между $$$u$$$ и $$$v$$$ в графе $$$F$$$ есть ребро. Гарантируется, что нет повторяющихся рёбер и петель.

Следующие $$$m_2$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u,v\leq n$$$) — между $$$u$$$ и $$$v$$$ в графе $$$G$$$ есть ребро. Гарантируется, что нет повторяющихся рёбер и петель.

Гарантируется, что сумма $$$n$$$, сумма $$$m_1$$$ и сумма $$$m_2$$$ по всем наборам входных данных не превышают $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество операций, необходимых на новой строке.

Пример
Входные данные
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$$$ должны быть оба удалены.