베시의 할아버지는 세계에서 가장 유명한 해적이었다. 그가 세상을 떠날 때 지금까지 모아두었던 보물들을 어느 동굴에 숨겨두었다.

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

각 통로의 길이는 모두 같으며, 각 통로들 끝은 막혀 있거나 2갈래의 갈림길이 있다. ( 1 <= 갈림길수(NP) <= 5,000) 그리고 T( 2 <= T <= P )번 통로 끝에 보물이 숨겨져 있다고 한다.

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

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

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

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

다음 줄 부터는 NS개의 갈림길의 정보가 주어진다.

첫 번째 값은 원래 통로이고 2~3번째 값은 각각 갈라지는 통로에 대한 정보를 나타낸다.

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

번역 : koistudy.net