문제
농부 존은 전염성이 강한 소 질병 COWVID-19가 발생한 이후 자신의 소들의 건강을 걱정하고 있습니다. 소들은 편의상 1번부터 N번까지 번호가 매겨져 있습니다.
최근 농부 존은 자신의 모든 소를 검사했고, 일부 소가 질병에 걸린 것을 확인했습니다. 헛간 내부의 영상 자료를 통해 최근 소들 간의 상호작용을 확인할 수 있었는데, 소들이 인사할 때 발굽을 부딪히는 행동(hooves shake)을 하는데, 불행히도 이 행동으로 질병이 전염될 수 있습니다.
농부 존은 시간 기록이 있는 소들의 상호작용 목록을 만들었습니다. 각 항목은 (t, x, y) 형태로, 이는 시간 t에 소 x와 소 y가 발굽을 부딪혔음을 의미합니다.
농부 존은 다음 사실도 알고 있습니다.
농장에서 질병을 처음 옮긴 소는 단 한 마리이며, 이 소를 "환자 제로(patient zero)"라고 부릅니다.
한 번 소가 감염되면, 그 소는 다음 K번의 발굽 인사 동안 감염을 전달할 수 있습니다. (같은 소와 여러 번 인사하는 경우도 포함) K번 이후에는 더 이상 감염을 전파하지 않습니다.
소가 감염되면 계속 감염 상태를 유지합니다.
불행하게도 농부 존은 어느 소가 환자 제로인지, 그리고 K값이 무엇인지 모릅니다.
데이터를 바탕으로 이 불확실성을 좁히는 것이 목표입니다. 최소한 하나의 가능성은 항상 존재한다고 보장됩니다.
입력
첫 번째 줄: N (2 ≤ N ≤ 100)과 T (1 ≤ T ≤ 250)
두 번째 줄: 길이가 N인 문자열, 각 문자는 0 또는 1, 농부 존의 소 상태를 나타냅니다. 0은 건강한 소, 1은 질병에 걸린 소입니다.
다음 T줄: 각각 세 개의 정수 t, x, y.
t: 상호작용이 발생한 시간 (t ≤ 250)
x, y: 발굽 인사를 한 서로 다른 소의 번호 (1…N)
한 시점에 하나의 상호작용만 존재합니다.
출력
한 줄에 세 개의 값을 출력합니다.
x: 환자 제로가 될 수 있는 소의 수
y: 데이터와 일치하는 K의 최소값
z: 데이터와 일치하는 K의 최대값 (만약 상한이 없으면 "Infinity" 출력)
K = 0도 가능할 수 있습니다.
예제
4 3
1100
7 1 2
5 2 3
6 2 4
1 1 Infinity
로그인해야 코드를 작성할 수 있어요.