Informatica Online Judge

  배로 여행하기 (Traveling Ship) [0503 / 01F7]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 65   Total Tried : 76


The Champion of this Problem (C++) : gs17018 - ms / 1048byte
My Best Submission (C++) : N/A

[]

Background

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

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

항구도시와 항로에 대한 정보가 주어졌을 때, S번 항구도시에서 T번 항구도시로 여행을 할 때 최대로 방문할 수 있는 항구도시의 개수를 구하는 프로그램을 작성하시오.

출발점 도착점을 포함한 각각의 항구도시는 여행 중에 몇 번이든 방문할 수 있으며, 같은 항로를 여러 번 이용할 수도 있다. 물론 같은 항구도시를 여러 번 방문하는 경우는 한 번만 생각하기로 한다.

Input

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

Output

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

* 테스트 데이터의 70%는 N이 100이하이다.

IO Example

입력
3 4 1 1
1 2
2 3
3 2
2 1

출력
3

* 설명 : 1-2-3-2-1의 순서로 이동하면 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]