시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 296 62 39 21.547%

문제

평소 일로 바쁘던 태희는 휴가를 통해 여행을 다녀오기로 하였다. 우선 태희는 사전 조사를 통해서 여행하려는 도시를 N(1≤N≤10,000)개 선택하였다. 태희는 비행기를 이용하면 충분히 여행할 수 있을거라 생각했지만, 짐을 꾸리던 중 비행기가 모든 도시들 사이를 다니는 것은 아님을 알게 되었다.

태희는 다시 비행로에 대해 조사를 하였고, 총 M(1≤M≤100,000)개의 비행로가 존재함을 알게 되었다. 각각의 비행로는 한 방향으로의 서비스만을 제공한다. 태희는 S(1≤S≤N)번 도시에서 시작해서 T(1≤T≤N)번 도시에서 여행을 끝내기로 하였다. 그리고 태희는 도시와 항공로에 대한 정보를 바탕으로 여행 계획을 세우기로 하였다.

도시와 비행로에 대한 정보가 주어졌을 때, S번 도시에서 T번 도시로 여행을 할 때 최대로 방문할 수 있는 도시의 개수를 구하는 프로그램을 작성하시오. 각각의 도시는 여행 중에 몇 번이든 방문할 수 있으며, 같은 항공로를 여러 번 이용할 수도 있다. 물론 같은 도시를 여러 번 방문하는 경우는 한 번만 생각하기로 한다.

입력

첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1≤A, B≤N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공로가 존재함을 의미한다.

출력

첫째 줄에 방문할 수 있는 도시의 최대 개수를 출력한다. 만약 여행 계획을 목표대로 세울 수 없다면 0을 출력한다.

예제 입력

3 4 1 1
1 2
2 3
3 2
2 1

예제 출력

3

힌트