Средний вес бусинки
Имеется 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 строк приведены два числа, означающих что первая бусинка тяжелее второй.
Выходные данные
Для каждого теста вывести в отдельной строке количество бусинок, которое однозначно не могут иметь средний вес.