농부 창호는 무서운 질병 소로나 바이러스(COWVID-19)로부터 자신의 소들을 보호하려고 애쓰고 있다.

최근에 농부 창호는 자신의 소들에게 바이러스 진단을 하였고, 몇몇 소들이 양성 반응을 보였음을 알아냈다.

창호는 헛간에 설치된 CCTV 영상을 통해서, 소들의 동선을 추적해보려고 한다.

비디오 영상을 통해서, 소들이 서로에게 반갑게 인사할 때 코뚜레(소들의 코에 껴져 있는 고리)를 비벼서 인사한다는 사실을 알아냈다.

불행히도 이 가까운 접촉을 허용하는 인사 방법으로 인해 바이러스가 다른 소에게로 전염된다는 사실 역시 알아냈다.

농부 창호는 영상을 통해 타임스탬프가 찍혀있는 소들의 행동 리스트를 정리했다.

이 리스트는 (t, x, y) 형식으로 써있는데, 이것은 t시점에 소 x와 소 y가 인사했다는 사실을 나타낸다.

농부 창호는 또한 다음과 같은 정보도 알고 있다:

- 최초 감염자(정확히는 감염우(牛, 소 우))는 한 마리뿐이다. 우리는 이를 “0번 확진자” 라고 부른다.

- 한번 바이러스에 감염된 소는 그 다음 K번의 인사 과정 중에 바이러스를 전염시킨다(K번 중에 같은 상대방 소와 여러 번 인사할 수도 있다.) 그 이후의 인사는 바이러스를 전염시키지 않는데, 그 이유는 이 시점부터 해당 소는 자신이 보균자라는걸 깨닫고 코뚜레를 깨끗이 씻기 때문이다.

- 코뚜레를 얼마나 잘 씻든지 간에, 한번 감염된 소는 감염된 채로 남는다.

불행히도, 농부 창호는 자신의 N마리의 소 중 어떤 소가 0번 확진자인지 모른다. 또한, 정수 K값이 얼마인지도 모른다.

창호를 대신해서 주어진 상황을 대신 분석해주어, 0번 확진자가 될 수 있는 소의 마릿수와, K값의 최솟값, K값의 최댓값을 각각 구하는 프로그램을 작성하라.

#3702 upload 4회 done 2회 how_to_reg 2명

소로나 바이러스 동선추적 timer 1초 memory 256MB

#3702

소로나 바이러스 동선추적 1초 256MB