Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных
1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео
(t,x,y), означающем, что в момент времени
t корова
x взаимодействовала с коровой
y. Также ФД знает следующее:
- Ровно одна корова была инфицирована изначально (нулевой пациент).
- После того, кaк корова инфицирована, она передаёт инфекцию её следующим K взаимодействиям (возможно включая одного и того же партнера несколько раз). После
K раз передачи инфекций, она перестаёт передавать инфекцию (осознав что заражает, она начинает тщательно мыть копыта).
- Однажды заболев, она остаётся больной.
К несчастью, ФД не знает, какая из его
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. В один момент времени
T происходит не более одного взаимодействия.
Выходные данные
Выведите одну строку, содержащую три целых числа
x,y,z, где
x - количество различных коров, которые могли быть "нулевым пациентом",
y - минимально возможное значение
K, подходящее к исходным данным,
z - наибольшее возможное значение
K, подходящее к исходным данным. Если для
K нет верхней границы, выведите "
Infinity" для
z. Заметим, что возможно
K=0.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4 |
1 1 Infinity |