Відстеження подій#10306

Відстеження подій

1 секунда

128 мегабайтів

Складна

Фермер Джон турбується про здоров'я своїх корів (пронумерованих від $1$ до $n$ ) після спалаху дуже заразної хвороби великої рогатої худоби COWVID-19.

Нещодавно фермер Джон перевірив усіх своїх корів і виявив, що деякі з них захворіли. Використовуючи відеозаписи з корівника, він може переглянути недавні взаємодії між парами корів. Виявляється, коли корови вітають одна одну, вони трясуть копитами — жест, який, на жаль, може передати інфекцію від однієї корови до іншої. Фермер Джон складає список контактуючих пар корів з позначками часу, використовуючи записи виду ( $t$ , $x$ , $y$ ), що означають, що в момент часу $t$ корова $x$ трясла своїми копитами з коровою $y$ . Фермер Джон також знає наступне:

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

(ii) Як тільки корова інфікована, вона передає інфекцію разом зі своїми наступними $k$ копитопотисками (можливо, кілька разів з однією і тією ж коровою-партнером). Після $k$ копитопотисків вона більше не передає інфекцію (в цей момент вона розуміє, що поширює інфекцію, і надалі при вітанні ретельно миє копита).

(iii) Після зараження корова залишається інфікованою.

На жаль, фермер Джон не знає, яка з його $n$ корів є нульовим пацієнтом, і не знає значення $k$ ! Допоможіть йому звузити можливості для пошуку цих невідомих на основі його даних. Гарантується, що хоча б одна можливість вірна.

Вхідні дані

Перший рядок містить числа $n$ ( $2 \leq n \leq 100$ 2 \leq n \leq 100) і $T$ ( $1 \leq T \leq 250$ 1 \leq T \leq 250). Наступний рядок має довжину $n$ , він містить $0$ і $1$ , описуючи поточний стан $n$ корів фермера Джона — $0$ позначає здорову корову, а $1$ позначає корову з хворобою. Кожен з наступних $T$ рядків описує контакт між коровами і складається з трьох цілих чисел $t$ , $x$ і $y$ , де $t$ ( $t \leq 250$ t \leq 250) — додатний цілий час контакту, а $x$ і $y$ — різні цілі числа в діапазоні $1 \dots n$ , номери корів, які потиснули одна одній копита в момент часу $t$ . У кожен момент часу відбувається не більше одного контакту.

Вихідні дані

Виведіть єдиний рядок з трьома цілими числами $x$ , $y$ і $z$ , де $x$ — кількість можливих корів, які могли бути нульовим пацієнтом, $y$ — найменше можливе значення $k$ відповідно до даних, а $z$ — максимально можливе значення $k$ , узгоджене з даними (якщо верхньої межі $k$ не існує, то виведіть "Infinity" для $z$ ). Зверніть увагу, що можливо $k = 0$ k = 0.

Приклади

Єдиний кандидат на нульового пацієнта — корова $1$ . Для всіх $k > 0$ k > 0 корова $1$ заражає корову $2$ в момент $7$ , а корови $3$ і $4$ залишаються неінфікованими.

Приклад 1