Problem
농부 John은 연속적으로 1…N으로 번호가 매겨진 소의 건강을 계속 돌보고 있습니다.
최근에 FD는 그들 모두를 확인했고 그들 중 일부가 아프다는 것을 알게 되었습니다. 헛간의 비디오를 사용하여 FD는 어떤 쌍의 젖소가 질병을 퍼뜨리기 위해 상호 작용했는지 알아낼 수 있습니다. FD는 비디오(t,x,y)에서 소 쌍의 상호 작용이 발생한 시간을 나타내는 목록을 수집했으며, 이는 시간 t 소 x가 소 y와 상호 작용했음을 의미합니다. FD는 또한 다음 사항을 알고 있습니다.
<올>
초기에는 정확히 한 마리의 소가 감염되었습니다(환자 0호).
소가 감염되면 다음 K 상호작용에 감염을 전달합니다(같은 파트너가 여러 번 관련될 수 있음). K번의 전파 후 그녀는 감염 전파를 멈춥니다(감염되었음을 깨닫고 발굽을 철저히 씻기 시작합니다).
한 번 아프면 아픈 상태를 유지합니다.
안타깝게도 PD는 자신의 N 소 중 어떤 것이 "Patient Zero"인지, K!의 가치를 알지 못합니다. 그의 데이터를 기반으로 이러한 미지의 범위를 좁힐 수 있도록 도와주세요. 정답은 반드시 존재합니다.
입력
첫 번째 입력 라인에는 N(2≤N≤100) 및 T(1≤T≤250)가 포함됩니다. 다음 줄에는 N FD 소의 현재 상태를 설명하는 0과 1로 구성된 길이 N의 문자열이 포함되어 있습니다(0 - 건강, 1 - 아프다). 다음의 각 T 행은 FD 상호 작용 목록의 항목을 설명하고 세 개의 숫자 t, x, y로 구성됩니다. 여기서 t는 양의 정수 상호 작용 시간(t≤250)이고 x와 y는 서로 다른 정수입니다. 간격 1…N, 시간 T에서 어떤 젖소가 상호 작용했는지 나타냅니다. 한 번에 T 시간에 하나 이상의 상호 작용이 발생하지 않습니다.
출판물
3개의 정수 x, y, z를 포함하는 한 줄을 인쇄합니다. 여기서 x는 "0 환자"가 될 수 있는 서로 다른 소의 수입니다. y - 입력 데이터에 맞는 가장 작은 K 값 z - 입력 데이터에 맞는 가장 큰 K 값 K에 대한 상한이 없으면 "Infinity"를 인쇄합니다. z를 위해. K=0이 가능하다는 점에 유의하십시오.
예
<헤드>
| # |
입력 |
출력 |
<몸>
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 무한대 |