Середня вага намистинки
Є N намистинок однакової форми та розміру, але різної ваги. Число N непарне, напистинки пронумеровано числами 1, 2, ..., N. Необхідно знайти намистинку з середньою (медіанною) вагою (((N+1)/2)-шу серед усіх намистинок). Можливо виконання наступної операції порівняння з парою намистин:
Для порівнянея ваг намистинок є терези. За їхньою допомогою можна визначити, яка з двох намистинок важча. Таким чином ми взнаємо, що одні з намистинок важчі інших. Тепер ми збираємось забрати деякі намистинки, які не можуть мати середню вагу.
Наприклад, наступні результати зважувань покажуть яка з намистинок важча після виконання M порівнянь, де M=4 та N=5.
Намистинка 2 важче намистинки 1.
Намистинка 4 важче намистинки 3.
Намистинка 5 важче намистинки 1.
Намистинка 4 важче намистинки 2.
З вище наведених результатів неможливо однозначно визначити середню за вагою намистинку, ми лише знаємо що намистинки 1 та 4 не можуть мати середню вагу: намистинки 2, 4, 5 важче намистинки 1, а намистинки 1, 2, 3 легші намистинки 4. Тому ми можемо видалити ці дві намистинки з розгляду.
Напишіть програму, яка підрахує кількість намистинок, які не можуть мати середню вагу.
Вхідні дані
Перший рядок містить кількість тестів t (1 ≤ t ≤ 11). Формат кожного тесту наступний: перший рядок містить кількість намистинок N (1 ≤ N ≤ 99) та кількість пар намистинок M, над якими проиведено порівняння. У кожному з наступних M рядків наведено два числа, які означають, що перша намистинка важча другої.
Вихідні дані
Для кожного тесту вивести у окремому рядку кількість намистинок, які однозначно не можуть мати середню вагу.