Отслеживание событий
Фермер Джон беспокоится за здоровье своих коров (последовательно пронумерованных 1 .. n) после вспышки очень заразной болезни крупного рогатого скота COWVID-19.
Недавно фермер Джон проверил всех своих коров и обнаружил, что у некоторых из них выявлено заболевание. Используя видеозаписи из коровника, он может просмотреть недавние взаимодействия между парами коров - оказывается, когда коровы приветствуют друг друга, они трясут копытами - жест, который, к сожалению, может передать инфекцию от одной коровы к другой. Фермер Джон составляет список контактирующих пар коров с отметками времени, используя записи вида (t, x, y), означающие что в момент времени t корова х трясла своими копытами с коровой у. Фермер Джон также знает следующее:
(i) Ровно одна корова на ферме могла начать переносить болезнь (назовем эту корову "нулевым пациентом").
(ii) Как только корова инфицирована, она передает инфекцию вместе своими следующими k копытопожатиями (возможно, несколько раз с одной и той же коровой-партнером). После k копытопожатий она больше не передает инфекцию (в этот момент она понимает, что распространяет инфекцию, и в дальнейшем при приветствии тщательно моет копыта).
(iii) После заражения корова остается инфицированной.
К сожалению, фермер Джон не знает, какая из его n коров является нулевым пациентом, и не знает значения k! Помогите ему сузить возможности для поиска этих неизвестных на основе его данных. Гарантируется, что хотя бы одна возможность верна.
Входные данные
Первая строка содержит числа n (2 ≤ n ≤ 100) и T (1 ≤ T ≤ 250). Следующая строка имеет длину n, она содержит 0 и 1, описывающие текущее состояние n коров фермера Джона - 0 обозначает здоровую корову, а 1 обозначает корову с заболеванием. Каждая из следующих T строк описывает контакт между коровами и состоит из трех целых чисел t, x и y, где t (t ≤ 250) - положительное целое время контакта, а x и y - различные целые числа в диапазоне 1 .. n, номера коров которые пожали друг другу копыта в момент времени t. В каждый момент времени происходит не более одного контакта.
Выходные данные
Выведите единственную строку с тремя целыми числами x, y и z, где x - количество возможных коров, которые могли быть нулевым пациентом, y - наименьшее возможное значение k в соответствии с данными, а z - максимально возможное значение k, согласованное с данными (если верхней границы k не существует, то выведите "Infinity" для z). Обратите внимание, что возможно k = 0.
Пример
Единственный кандидат на нулевого пациента - корова 1. Для всех k > 0 корова 1 заражает корову 2 в момент 7, а коровы 3 и 4 остаются неинфицированными. .