Погоня за акціями#1277
Запроваджується нове регулювання ринку: жодна компанія не може контролювати власні акції, ні прямо, ні опосередковано. Біржовий регулятор шукає комп'ютерне рішення, яке допоможе йому виявляти будь-яку покупку, яка призведе до того, що компанія контролюватиме свої ж акції. Причина, чому їм потрібна така програма, очевидна — уявіть ситуацію, коли компанія купує акції компанії , купує у , а потім купує у . Перші дві покупки прийнятні.
Третю покупку слід відхилити, оскільки вона призведе до того, що всі три компанії контролюватимуть власні акції. Програмі будуть передані всі транзакції купівлі у хронологічному порядку. Програма повинна відхиляти будь-яку транзакцію, яка може призвести до того, що компанія контролюватиме власні акції.
Усі інші транзакції приймаються.
Ваша програма проходитиме тестування на одному або декількох тестових наборах. Кожен тестовий набір задається на T+1 рядках. У першому рядку вказані два додатних числа: (0 < N \leq 234) — кількість компаній і (0 < T \leq 100\,000) — кількість транзакцій. Далі йдуть рядків, кожен з яких описує одну транзакцію купівлі. Кожна транзакція задається двома числами і , де (0 < A,\ B \leq N) означає, що компанія хоче купити акції компанії .
Останній рядок вхідного файлу містить два нулі.
Для кожного тесту виведіть такий рядок:
.
де — номер тесту (починаючи з одиниці), — кількість транзакцій, які слід відхилити.
Примітка: Перед має бути пробіл.
Приклад 1