Щасливі міста#1369
Джон нещодавно прибув до Румунії на Південно-Східноєвропейські регіональні змагання. Джон ніколи раніше не був у Румунії, тому місцеві жителі вирішили організувати для нього екскурсію містами. Ця екскурсія охоплюватиме декілька румунських міст, і кожне місто буде відвідано не більше одного разу. Джон почне з одного міста, відвідає інші міста згідно з маршрутом екскурсії, і завершить тур, повернувшись до початкового міста.
У країні міст, пронумерованих від до , і двосторонніх доріг. Кожна дорога з'єднує два різні міста. Розглянемо туристичний маршрут для Джона: c_1, c_2, \ldots, c_n, де кожне c_i — це місто Румунії. Всі c_i повинні бути різними. Для кожного i = 1, 2, \ldots, n-1 має існувати дорога між c_i та c_{i+1}, а також дорога між c_n та c_1.
Джон — незвичайна людина і хоче відвідати непарну кількість міст. Організатори спланували всі можливі маршрути, які охоплюють непарну кількість міст. Місто називається щасливим, якщо існує хоча б один маршрут, що проходить через нього. Ваше завдання — підрахувати кількість щасливих міст у Румунії.
У першому рядку знаходиться одне ціле число — кількість тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілих числа і , розділених пробілом. Кожен із наступних рядків містить два цілих числа a_i та b_i, розділених пробілом, які позначають міста, з'єднані -ю дорогою.
Обмеження: 1 \le T \le 77, 0 \le N, M \le 100\,000 (10^5), 1 \le a_i < b_i \le N.
Виведіть рядків, у кожному з яких має бути відповідь для відповідного тесту.
Приклад 1