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

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

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

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

(1 <= 갈림길 수(NS) <= 5,000)와 보물이 숨겨진 통로 번호 T(2 ≤ T ≤ P)가 주어진다.

보물은 T번 통로 끝에 있다.

다음은 한 입력 예를 그림으로 그린 것이다.

위 그림의 경우 13개의 통로를 가지며 6개의 갈림길을 가지는 한 예이다.

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

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

이 경우에 보물로 가는 가장 짧은 경로는 1−2−4−6−7로 5단계 이동으로 보물을 찾을 수 있다.

보물동굴-Treasure Cave(보물 찾기) timer 1s memory 128MB

보물동굴-Treasure Cave(보물 찾기) 1s 128MB