문제
농부 창호는 무서운 질병 소로나 바이러스(COWVID-19)로부터 자신의 소들을 보호하려고 애쓰고 있다.
최근에 농부 창호는 자신의 소들에게 바이러스 진단을 하였고, 몇몇 소들이 양성 반응을 보였음을 알아냈다.
창호는 헛간에 설치된 CCTV 영상을 통해서, 소들의 동선을 추적해보려고 한다.
비디오 영상을 통해서, 소들이 서로에게 반갑게 인사할 때 코뚜레(소들의 코에 껴져 있는 고리)를 비벼서 인사한다는 사실을 알아냈다.
불행히도 이 가까운 접촉을 허용하는 인사 방법으로 인해 바이러스가 다른 소에게로 전염된다는 사실 역시 알아냈다.
농부 창호는 영상을 통해 타임스탬프가 찍혀있는 소들의 행동 리스트를 정리했다.
이 리스트는 (t, x, y) 형식으로 써있는데, 이것은 t시점에 소 x와 소 y가 인사했다는 사실을 나타낸다.
농부 창호는 또한 다음과 같은 정보도 알고 있다:
- 최초 감염자(정확히는 감염우(牛, 소 우))는 한 마리뿐이다. 우리는 이를 “0번 확진자” 라고 부른다.
- 한번 바이러스에 감염된 소는 그 다음 K번의 인사 과정 중에 바이러스를 전염시킨다(K번 중에 같은 상대방 소와 여러 번 인사할 수도 있다.) 그 이후의 인사는 바이러스를 전염시키지 않는데, 그 이유는 이 시점부터 해당 소는 자신이 보균자라는걸 깨닫고 코뚜레를 깨끗이 씻기 때문이다.
- 코뚜레를 얼마나 잘 씻든지 간에, 한번 감염된 소는 감염된 채로 남는다.
불행히도, 농부 창호는 자신의 N마리의 소 중 어떤 소가 0번 확진자인지 모른다. 또한, 정수 K값이 얼마인지도 모른다.
창호를 대신해서 주어진 상황을 대신 분석해주어, 0번 확진자가 될 수 있는 소의 마릿수와, K값의 최솟값, K값의 최댓값을 각각 구하는 프로그램을 작성하라.
입력
첫 줄에는 정수 N과 T가 공백을 사이에 두고 주어진다. (1≤N≤100, 1≤T≤250).
다음 줄에는 길이 N의 0과 1로 이루어진 문자열이 주어지며, 이는 1번부터 n번까지 각 소들의 감염 여부를 나타낸다.
0은 감염되지 않은 소이며, 1은 감염된 소이다.
다음 T 줄에 걸쳐서, t x y 형식으로 이루어진 리스트 정보가 주어진다.
이는 t시점에 x번 소와 y번 소가 접촉해서 인사했다는 것을 뜻한다.
같은 시점에는 한 가지 사건만 일어난다.
(1≤t≤250 , 1≤x,y≤N)
출력
한 줄에 세 정수를 공백으로 구분하여 출력한다.
첫 번째 정수는 “0번 확진자”가 될 수 있는 소의 총 마릿수이며, 두 번째는 K값의 최솟값, 세 번째는 K값의 최댓값이다.
세 번째 정수의 경우, K값의 상한이 없을 경우(즉 K값이 무한히 커질 수 있는 경우) Infinity를 출력한다.
K값이 0이 될 수 있음에 유의한다.
예제1
4 3
1100
7 1 2
5 2 3
6 2 4
1 1 Infinity