Informatica Online Judge

  공주를 구해라. [1404 / 057C]

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


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

[]

Background

재민이는 정과프 시간에 왕자가 산봉우리에 있는 공주를 빨리 구하는 게임 프로그램을 개발하고자 한다.

공주가 갇혀있는 곳은 중국 장가계와 같은 산봉우리 위에 있으며, 재민이는 왕자가 산봉우리와 산봉우리 사이의 구름다리를 건너가 공주를 구할 수 있도록 설계하였다.

구름다리의 길이는 같다.

단, 왕자는 하늘을 날거나 산 아래로 내려갈 수는 없다.

예를 들어, 5개의 산봉우리가 있고, 구름다리는 1-2, 1-3, 2-3, 3-5, 4번-5번 산봉우리에 설치되어 있다.

만약 왕자가 1번 산봉우리, 공주는 4번 산봉우리에 있다면, 왕자가 공주를 구할 수 있는 가장 빠른 방법은 1번 -> 3번 -> 5번 -> 4번 산봉우리로, 구름다리를 3번 건너면 된다.

물론, 1-> 2-> 3-> 5-> 4 로 건너가서 공주를 구할수도 있지만, 그렇게 되면 구름다리를 4번 건너게 되어 그 레벨을 통과할 수 없다.

재민이는 게임의 극대화를 위해 산봉우리 개수, 구름다리가 연결된 산봉우리들, 왕자 및 공주 위치를 랜덤으로 변경해 레벨을 주고 싶다.

단, 재민이가 산봉우리 구름다리, 왕자, 공주 위치를 랜덤으로 설계하다보니, 가끔 왕자가 공주에게 아예 가지 못하는 경우가 생기는 것을 발견했다.

재민이가 랜덤으로 게임 입력 데이터를 설계했을 때, 최소 몇 번만에 공주를 구할 수 있는지 구하고, 만약 공주에게 가지 못하면 0을 출력하는 프로그램을 작성하고자 한다.

Input

첫 번째 줄은 산봉우리 개수(1<=N<=3,500), 구름다리 개수(1<=M<=1,000,000)를 입력한다.

두 번째 줄부터 구름다리가 연결된 산 번호 2개를 공백을 두고 M개만큼 입력한다.

마지막 줄은 왕자의 시작 위치(S), 공주 위치(E)를 입력한다.

Output

왕자가 공주에게 갈 수 있는 가장 짧은 구름다리 개수를 출력한다. 단, 공주에게 갈 수 없으면 0을 출력한다.

IO Example

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

출력1
3

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

출력2
0

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