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