지원 알림의 마지막 도착지

문제

한 회사의 IT 지원팀은 사내 장비에 점검 알림을 전달하는 시험을 진행한다. 시험 대상 장비는 1번부터 N번까지 번호가 붙어 있다. 일부 장비 사이에는 알림을 전달하는 단방향 연결이 설정되어 있다. 연결 a → b는 a번 장비가 받은 알림을 b번 장비로 전달할 수 있다는 뜻이다. 반대 방향의 전달도 가능하다는 뜻은 아니므로, 반대로 전달하려면 별도의 연결이 필요하다. 시험을 시작하는 시각은 0이며, 이때 S번 장비만 알림을 받는다. 알림을 처음 받은 장비는 자신에게서 나가는 모든 연결을 통해 즉시 알림을 보낸다. 각 연결을 통과하는 데에는 정확히 1의 시간이 걸린다. 여러 연결에서 보내는 알림은 동시에 이동할 수 있으며, 다른 장비의 전송 때문에 기다리는 일은 없다. 한 장비가 알림을 여러 번 받더라도 처음 받은 시각만 기록하고, 이후 도착한 알림으로 다시 전송하지 않는다. 지원팀은 시험 결과에서 두 가지 정보를 확인하려 한다. 첫째는 알림을 받은 장비 중 처음 받은 시각이 가장 늦은 장비와 그 시각이다. 같은 시각에 처음 알림을 받은 장비가 여러 대라면 번호가 가장 작은 장비를 선택한다. 둘째는 시험을 아무리 오래 진행해도 알림을 받지 못하는 장비의 수다. 전달 경로가 없는 장비는 첫째 정보를 정할 때 후보에 포함하지 않는다. 시작 장비 S도 알림을 받은 장비에 포함하며, 그 장비가 처음 받은 시각은 항상 0이다. 따라서 연결이 하나도 없거나 S에서 다른 장비로 알림을 보낼 수 없는 경우에는 S가 선택된다. 서로 다른 연결을 따라 알림이 되돌아오는 상황도 있을 수 있지만, 이미 기록된 최초 수신 시각은 바뀌지 않는다. 장비 목록과 단방향 연결이 주어질 때, 지원팀이 확인하려는 장비 번호, 최초 수신 시각, 미수신 장비 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, M, S가 공백으로 주어진다. 다음 M개 줄에 단방향 연결을 나타내는 정수 a와 b가 공백으로 주어진다.
1 ≤ N ≤ 20,000, 0 ≤ M ≤ 20,000, 1 ≤ S ≤ N, 1 ≤ a, b ≤ N이며 a ≠ b이다. 같은 순서쌍 (a, b)는 두 번 주어지지 않는다.

출력

선택된 장비 번호, 그 장비의 최초 수신 시각, 알림을 받지 못하는 장비의 수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 최초 수신 시각이 가장 늦은 장비가 여러 대라면 번호가 가장 작은 장비를 출력한다.

6 5 1
1 2
1 3
2 4
3 5
5 3

4 2 1

3 2 2
1 2
3 1

2 0 2

1 0 1

1 0 0

출처: Devin.KR 자체 제작