Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0227 - ГОНКИ

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

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

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

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

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

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

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

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

Примеры

stdin

stdout

1

1
3 3
1 2
2 3
1 3

3


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.East Sibirean QF 2014.D

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.