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