Даны два простых неориентированных графа \(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\).
Выходные данные
Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество операций, необходимых на новой строке.
Примечание
В первом наборе входных данных вы можете выполнить следующие три операции:
- Добавить ребро между вершиной \(1\) и вершиной \(3\).
- Удалить ребро между вершиной \(1\) и вершиной \(2\).
- Удалить ребро между вершиной \(2\) и вершиной \(3\).
Можно показать, что меньшее количество операций невозможно достичь.
Во втором наборе входных данных графы \(F\) и \(G\) уже изначально удовлетворяют условию.
В пятом наборе входных данных рёбра от \(1\) до \(3\) и от \(2\) до \(3\) должны быть оба удалены.
Примеры
| № | Входные данные | Выходные данные |
|
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
|