eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Безопасный полет

Безопасный полет

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
prb6422

В настоящее время из-за сокращения бюджета даже шпионы должны использовать коммерческие авиакомпании для путешествия между городами в мире. Хотя этот режим поездок может быть и очень удобным для шпиона, однако также создает проблему: шпион должен доверять пилоту - то есть убедиться, что он не находится в опасности во время полета. И даже хуже: иногда нет прямого рейса между некоторыми парами городов, так что шпион должен лететь несколькими рейсами, чтобы добраться до нужного места, вследствие чего он должен доверять нескольким пилотам!

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

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

Первая строка содержит количество тестов, которое не больше 100. Далее для каждого теста:

  • в одной строке содержится количество городов n (2n1000) и пилотов m (1m10000).

  • m строк с числами a и b (1a, bn, ab): пилот летает между городами a и b туда и обратно.

Путешествовать между городами можно пользуясь одним или несколькими перелетами. Граф является связным.

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

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

Пример

Входные данные #1
2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5
Выходные данные #1
2
4
Источник The 2013 Benelux Algorithm Programming Contest, BAPC 2013