Задача
Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных 1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео (t,x,y), означающем, что в момент времени t корова x взаимодействовала с коровой y. Также ФД знает следующее:
- Ровно одна корова была инфицирована изначально (нулевой пациент).
- После того, кк корова инфицирована, она передаёт инфекцию её следующим 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 |