Мінімізація ребер
У Бесі є зв'язний ненаправлений граф G з n вершинами, позначеними від 1 до n, і m ребрами. Граф G може містити петлі (ребра, що починаються і закінчуються в одній і тій же вершині), але не має паралельних ребер (декілька ребер між одними і тими ж вершинами).
Нехай fG(a, b) — це булева функція, яка повертає істину, якщо існує шлях від вершини 1 до вершини a, що проходить рівно b ребер, для 1 ≤ a ≤ n і 0 ≤ b. В іншому випадку функція повертає хибність. Якщо по ребру проходять кілька разів, це враховується в підрахунку.
Ельза хоче повторити за Бесею. Вона прагне створити ненаправлений граф G′ такий, що fG′(a, b) = fG(a, b) для всіх a і b.
Ельза хоче виконати мінімум роботи, тому вона прагне створити граф з мінімально можливою кількістю ребер. Ваше завдання — обчислити мінімально можливу кількість ребер у G′.
Кожен вхід містить t тестів, які потрібно вирішувати незалежно. Гарантується, що сума n по всіх тестах не перевищує 10^5, а сума m по всіх тестах не перевищує 2 * 10^5.
Вхідні дані
Перша стрічка вводу містить кількість тестів t (1 ≤ t ≤ 5 * 10^4).
Перша стрічка кожного тесту містить два цілі числа n і m (2 ≤ n ≤ 10^5, n − 1 ≤ m ≤ (n^2 + n) / **2`).
Наступні m рядків кожного тесту містять два цілі числа x і y (1 ≤ x ≤ y ≤ n), що позначають ребро між x і y в G.
Послідовні тести розділені пустим рядком для зручності читання.
Вихідні дані
Для кожного тесту виведіть мінімально можливу кількість ребер у G′ в окремому рядку.
Приклад
У першому тесті, Ельза може сконструювати G′, почавши з G і видаливши ребро (2, 5). Або може сконструювати граф з наступними ребрами:
1 2 1 4 4 3 4 5
оскільки вона не обмежена лише видаленням ребер з G: Ельза безумовно не може зробити менше ніж n − 1 ребро, оскільки граф G′ також повинен бути зв'язним.