Відстеження подій
Фермер Джон турбується про здоров'я своїх корів (пронумерованих від 1 до n) після спалаху дуже заразної хвороби великої рогатої худоби COWVID-19.
Нещодавно фермер Джон перевірив усіх своїх корів і виявив, що деякі з них захворіли. Використовуючи відеозаписи з корівника, він може переглянути недавні взаємодії між парами корів. Виявляється, коли корови вітають одна одну, вони трясуть копитами — жест, який, на жаль, може передати інфекцію від однієї корови до іншої. Фермер Джон складає список контактуючих пар корів з позначками часу, використовуючи записи виду (t, x, y), що означають, що в момент часу t корова x трясла своїми копитами з коровою y. Фермер Джон також знає наступне:
(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 залишаються неінфікованими.