Безпечний політ
Через скорочення бюджету навіть шпигуни змушені користуватися послугами комерційних авіакомпаній для подорожей між містами світу. Хоча такий спосіб пересування може бути зручним, він також створює проблему: шпигун повинен довіряти пілоту, тобто бути впевненим у своїй безпеці під час польоту. Ще гірше, коли між деякими парами міст немає прямого рейсу, і шпигун змушений летіти кількома рейсами, довіряючи кільком пілотам.
Щоб зменшити кількість питань довіри, ви звернулися за допомогою. На основі наявного розкладу польотів потрібно знайти найменший набір пілотів, яким слід довіряти, щоб шпигун міг безпечно подорожувати між усіма містами.
Вхідні дані
Перший рядок містить кількість тестів, не більше 100. Далі для кожного тесту:
в одному рядку вказано кількість міст n (2 ≤ n ≤ 1000) і пілотів m (1 ≤ m ≤ 10000).
m рядків з числами a і b (1 ≤ a, b ≤ n, a ≠ b): пілот літає між містами a і b в обидва напрямки.
Подорожувати між містами можна, використовуючи один або кілька перельотів. Граф є зв'язним.
Вихідні дані
Для кожного тесту в окремому рядку вивести найменшу кількість пілотів, яким слід довіряти шпигуну, щоб мати можливість подорожувати між будь-якою парою міст.