SPOJ in Gyumri

Президент страны Амберландии решил поправить сильно поблекшую международную репутацию своей страны. Для этого он хочет провести в Амберландии этап международной гоночной серии «Формула 42». Однако дела в национальной экономике идут не очень, и денег в бюджете на строительство специальной трассы нет совсем.

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

Схема дорог Амберландии состоит из N перекрестков и M двухсторонних дорог, соединяющих перекрестки. Между парой перекрестков не может быть больше одной дороги; также не бывает дорог соединяющих перекресток с самим собой. Замкнутым маршрутом называется последовательность перекрестков c₁, c₂, c₃, ... , c_k, c₁ таких, что в дорожной системе страны присутствуют дороги (c₁, c₂), (c₂, c₃), ... , (c_k, c₁). В целях безопасности маршрут может проходить через каждую дорогу не больше одного раза. 

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

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

Первая строка входных данных содержит количество тестов T (T ≤ 20). Первая строка каждого теста содержит числа N и M (1 ≤ N ≤ 200, 1 ≤ M ≤ 1000). Далее следуют M строк, описывающих дороги. Каждая такая строка содержит пару чисел A и B, обозначающих номера перекрёстков, соединённых соответствующей дорогой (1 ≤ A, B ≤ N). Все числа внутри строки разделяются пробелами. Гарантируется, что сумма всех M во входном файле не превосходит 7500.

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

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

Примеры