eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Отслеживание событий

Отслеживание событий

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Фермер Джон беспокоится за здоровье своих коров (последовательно пронумерованных 1 .. n) после вспышки очень заразной болезни крупного рогатого скота COWVID-19.

Недавно фермер Джон проверил всех своих коров и обнаружил, что у некоторых из них выявлено заболевание. Используя видеозаписи из коровника, он может просмотреть недавние взаимодействия между парами коров - оказывается, когда коровы приветствуют друг друга, они трясут копытами - жест, который, к сожалению, может передать инфекцию от одной коровы к другой. Фермер Джон составляет список контактирующих пар коров с отметками времени, используя записи вида (t, x, y), означающие что в момент времени t корова х трясла своими копытами с коровой у. Фермер Джон также знает следующее:

(i) Ровно одна корова на ферме могла начать переносить болезнь (назовем эту корову "нулевым пациентом").

(ii) Как только корова инфицирована, она передает инфекцию вместе своими следующими k копытопожатиями (возможно, несколько раз с одной и той же коровой-партнером). После k копытопожатий она больше не передает инфекцию (в этот момент она понимает, что распространяет инфекцию, и в дальнейшем при приветствии тщательно моет копыта).

(iii) После заражения корова остается инфицированной.

К сожалению, фермер Джон не знает, какая из его n коров является нулевым пациентом, и не знает значения k! Помогите ему сузить возможности для поиска этих неизвестных на основе его данных. Гарантируется, что хотя бы одна возможность верна.

Входные данные

Первая строка содержит числа n (2n100) и T (1T250). Следующая строка имеет длину n, она содержит 0 и 1, описывающие текущее состояние n коров фермера Джона - 0 обозначает здоровую корову, а 1 обозначает корову с заболеванием. Каждая из следующих T строк описывает контакт между коровами и состоит из трех целых чисел t, x и y, где t (t250) - положительное целое время контакта, а 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 остаются неинфицированными. .

Пример

Входные данные #1
4 3
1100
7 1 2
5 2 3
6 2 4
Выходные данные #1
1 1 Infinity
Источник 2020 USACO US Open, Бронза