Мінімізація ребер#11217

Мінімізація ребер

1 секунда

128 мегабайтів

Дуже складна

У Бессі є зв'язний неорієнтований граф $G$ з $n$ вершинами, позначеними $1, 2, \dots, n$ 1, 2, \ldots, n, і $m$ ребрами. Граф $G$ може містити петлі (ребра, що починаються й закінчуються в одній вершині), але не має паралельних ребер (декілька ребер між одними й тими ж вершинами).

Нехай $f_{G} (a, b)$ f_G(a, b) — це булева функція, яка повертає істину, якщо існує шлях від вершини $1$ до вершини $a$ , що проходить рівно $b$ ребер ( $1 \leq a \leq n$ 1 \le a \le n, $0 \leq b$ 0 \le b). В іншому випадку функція повертає хибність. Якщо по ребру проходять кілька разів — це враховується в підрахунку.

Ельза хоче повторити за Бессі. Вона прагне створити неорієнтований граф $G^{'}$ G' такий, що $f_{G^{'}} (a, b) = f_{G} (a, b)$ f_{G'}(a, b) = f_G(a, b) для всіх $a$ і $b$ .

Ельза хоче виконати мінімум роботи, тому вона прагне створити граф з мінімальною можливою кількістю ребер. Ваше завдання — порахувати мінімальну можливу кількість ребер у $G^{'}$ G'.

Гарантується, що сума $n$ по всіх тестах не перевищує $1 0^{5}$ 10^5, а сума $m$ по всіх тестах не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вхідні дані

Перша стрічка містить $t$ ( $1 \leq t \leq 5 \cdot 1 0^{4}$ 1 \le t \le 5 \cdot 10^4) — кількість тестів.

Перша стрічка кожного тесту містить два цілих числа $n$ і $m$ ( $2 \leq n \leq 1 0^{5}$ 2 \le n \le 10^5, $n - 1 \leq m \leq \frac{n ^{2} + n}{2}$ n - 1 \le m \le \frac{n^2 + n}{2}).

Наступні $m$ рядків кожного тесту містять два цілі числа $x$ і $y$ ( $1 \leq x \leq y \leq n$ 1 \le x \le y \le n), що позначають ребро між $x$ і $y$ в $G$ .

Послідовні тести розділені порожнім рядком для зручності читання.

Вихідні дані

Для кожного тесту виведіть мінімально можливу кількість ребер у $G^{'}$ G' в окремому рядку.

Приклади

У першому тесті, Ельза може сконструювати $G^{'}$ G' почавши з $G$ і видаливши ребро $(2, 5)$ . Або може сконструювати граф з наступними ребрами, оскільки вона не обмежена лише видаленням ребер з $G$ :

Ельза не може зробити краще, ніж $n - 1$ n - 1 ребро, оскільки граф $G^{'}$ G' також повинен бути зв'язним.

Приклад 1