전달을 멈춘 메신저

문제

한 회사의 사내 메신저에는 직원 사이에 등록된 대화 연결이 있다. 대화 연결은 양방향이므로, 두 직원이 연결되어 있으면 어느 쪽에서든 다른 쪽으로 공지를 보낼 수 있다. 직원 번호는 1번부터 N번까지다. 공지는 직접 연결된 직원에게만 한 번에 전달할 수 있으며, 연결 하나를 지나는 데 정확히 1분이 걸린다. 일부 직원은 메신저의 자동 전달 기능을 꺼 두었다. 자동 전달 기능이 꺼진 직원도 공지를 받을 수 있지만, 받은 공지를 다른 직원에게 전달하지는 않는다. 자동 전달 기능이 켜진 직원은 공지를 처음 받은 즉시 자신과 직접 연결된 모든 직원에게 전달한다. 여러 직원에게 보내는 작업은 동시에 이루어지므로 연결된 직원 수에 따라 시간이 늘어나지는 않는다. 0분에 S번 직원이 공지를 처음 가지고 있다. S번 직원도 다른 직원과 똑같이 자신의 자동 전달 설정을 따른다. 따라서 S번 직원의 자동 전달 기능이 꺼져 있다면 다른 직원에게 공지를 보내지 않는다. 이미 공지를 받은 직원에게 같은 공지가 다시 도착해도 최초 수신 시각은 바뀌지 않으며, 다시 전달 작업을 시작하지도 않는다. 같은 시각에 여러 경로로 처음 공지가 도착하는 경우도 한 번 받은 것으로 센다. 운영 담당자는 공지가 퍼지는 속도와 끝내 전달되지 않는 범위를 확인하려 한다. 최초 수신 시각이 정확히 K분인 직원의 수와, 시간이 충분히 지나도 공지를 받지 못하는 직원의 수를 구한다. S번 직원의 최초 수신 시각은 항상 0분이며, 두 종류의 집계 모두 전체 N명의 직원을 대상으로 한다. 특정 조건을 만족하는 직원이 없으면 해당 인원수는 0이다. 입력에는 자기 자신과의 연결이나 같은 두 직원 사이의 중복 연결이 없다.

입력

첫째 줄에 직원 수 N, 대화 연결 수 M, 처음 공지를 가진 직원 번호 S, 조사할 시각 K가 공백으로 주어진다.
둘째 줄에 길이가 N인 문자열이 주어진다. i번째 문자가 1이면 i번 직원의 자동 전달 기능이 켜져 있고, 0이면 꺼져 있다.
다음 M개 줄에 대화 연결의 양 끝 직원 번호 u와 v가 공백으로 주어진다.
N, M, S, K, u, v는 정수이며 1 ≤ N ≤ 12,000, 0 ≤ M ≤ min(24,000, N(N-1)/2), 1 ≤ S ≤ N, 0 ≤ K ≤ N-1, 1 ≤ u, v ≤ N, u ≠ v다. 각 무순서 쌍 {u, v}는 최대 한 번 주어진다.

출력

최초 수신 시각이 정확히 K분인 직원 수와 끝내 공지를 받지 못하는 직원 수를 이 순서로 공백으로 구분하여 한 줄에 출력한다.

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

1 1

4 3 2 0
1011
1 2
2 3
3 4

1 3

1 0 1 0
1

1 0

출처: Devin.KR 자체 제작