Informatica Online Judge

  보물 찾기 [0210 / 00D2]

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


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

[]

Background

베시의 할아버지는 세계에서 가장 유명한 해적이었다.

그가 세상을 떠날 때 지금까지 모아두었던 보물들을 어느 동굴에 숨겨두었다.

동굴은 $1$ ~ $P$까지의 번호가 붙은 $P$개($3 ≤ P ≤ 5,000$)의 통로로 구성되어 있으며 통로 $1$이 입구이다.

각 통로의 길이는 모두 같으며, 각 통로들 끝은 막혀 있거나 $2$갈래의 갈림길이 있다.

($1 <=$ 갈림길수($NS$) $<= 5,000$) 그리고 $T$($2 ≤ T ≤ P $)번 통로 끝에 보물이 숨겨져 있다고 한다.

다음은 한 동굴의 예를 나타낸다.



각 번호는 통로를 나타내고 "+"기호는 갈림길을 의미하며 "#"은 보물의 위치를 의미한다.

주어진 모든 구조는 항상 트리임을 보장한다.

위의 경우 $13$개의 통로를 가지며 $6$개의 갈림길을 가지는 한 예이다. 이 경우에 보물로 가는 가장 짧은 경로는 $1-2-4-6-7$로 $5$단계 이동으로 가능하다.

Input

세 개의 정수$P$(통로 수), $NS$(갈림길 수), $T$(보물의 위치)가 주어진다.

다음 줄 부터는 $NS$개의 갈림길의 정보가 주어진다. 첫 번째 값은 원래 통로이고 $2$~$3$번째 값은 각각 갈라지는 통로에 대한 정보를 나타낸다.

Output

보물로 가는 가장 짧은 단계 수와 그 통로를 한 줄에 하나씩 출력한다.

IO Example

입력
13 6 7
6 7 8
2 3 4
10 11 12
8 9 10
1 2 13
4 5 6

출력
5
1
2
4
6
7


출처 : USACO (http://ace.delos.com)

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