공지의 전달 단계

문제

한 회사의 사내 메신저에는 직원이 다른 직원에게 공지를 자동 전달하도록 설정하는 기능이 있다. 직원마다 자동 전달 대상이 다르며, 어떤 직원이 다른 직원을 대상으로 등록했다고 해서 반대 방향의 전달도 가능한 것은 아니다. 운영 담당자는 중요한 공지가 어느 정도의 전달 단계를 거쳐 퍼지는지 확인하려 한다. 직원에게는 1번부터 N번까지 번호가 붙어 있다. 자동 전달 설정 하나는 두 직원 번호 u와 v로 나타낸다. 이는 u번 직원이 공지를 처음 받으면 v번 직원에게 전달한다는 뜻이다. 같은 설정이 여러 번 입력될 수 있고, 자기 자신에게 전달하는 설정도 있을 수 있다. 이러한 설정도 다른 설정과 동일하게 취급한다. 처음에는 S번 직원만 공지를 가지고 있다. S번 직원이 공지를 받은 단계는 0이다. 어떤 직원이 단계 d에서 처음 공지를 받았다면, 그 직원의 모든 자동 전달 대상은 단계 d+1에 공지를 받을 수 있다. 여러 경로로 같은 직원에게 공지가 도착하더라도 그 직원은 가장 이른 단계에 한 번만 공지를 받은 것으로 기록한다. 이미 받은 공지를 나중에 다시 받는 일은 그 직원의 기록을 바꾸거나 추가 전달을 발생시키지 않는다. 예를 들어 한 직원에게 두 번 전달하는 경로와 네 번 전달하는 경로가 모두 있다면, 그 직원의 기록은 2단계이다. 네 번 전달하는 경로가 존재한다는 이유로 4단계 직원에 포함하지 않는다. 어떤 경로로도 공지를 받을 수 없는 직원에게는 전달 단계가 없다. 담당자가 지정한 음이 아닌 정수 K에 대하여, 처음 공지를 받은 단계가 정확히 K인 직원의 수를 구한다. 직원 번호의 크기나 전달 설정의 입력 순서는 결과에 영향을 주지 않는다. K가 0이면 최초 발신자인 S번 직원만 센다. 해당 단계에 처음 공지를 받은 직원이 없으면 0을 출력한다.

입력

첫째 줄에 정수 N, M, S, K가 공백으로 주어진다. 1 ≤ N ≤ 20,000, 0 ≤ M ≤ 28,000, 1 ≤ S ≤ N, 0 ≤ K ≤ N이다.
다음 M개 줄에 자동 전달 설정을 나타내는 정수 u, v가 공백으로 주어진다. 1 ≤ u, v ≤ N이다. 중복 설정과 u = v인 설정이 허용된다.

출력

처음 공지를 받은 단계가 정확히 K인 직원의 수를 정수 하나로 출력한다.

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

2

3 2 2 0
2 2
1 3

1

4 2 1 3
1 2
2 1

0

출처: Devin.KR 자체 제작