Stock Chase
Я признаю, что предложенное мной в прошлом году решение для устранения кризиса наличности в банке не смогло полностью разрешить экономический кризис. Как выяснилось, у компаний изначально не так много наличных средств.
У них есть активы, которые в основном состоят из акций других компаний. Это обычная и приемлемая практика, когда одна компания владеет акциями другой. Ситуация усложняется, когда две компании одновременно владеют акциями друг друга. Если задуматься, это означает, что каждая компания теперь (косвенно) контролирует свои собственные акции.
Вводится новое рыночное регулирование: ни одна компания не может контролировать акции в себе, будь то напрямую или косвенно. Фондовая биржа ищет компьютерное решение, которое поможет ей выявлять любую покупательскую активность, которая приведет к тому, что компания будет контролировать свои собственные акции. Очевидно, почему им нужна программа для этого, просто представьте ситуацию, когда компания 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 есть пробел.