문제
농부 존의 할아버지는 세계에서 가장 유명한 해적이었다.
그가 세상을 떠날 때 지금까지 모아두었던 보물들을 어느 동굴에 숨겨두었다.
동굴은 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단계 이동으로 보물을 찾을 수 있다.
입력
첫 행에 세 개의 정수P(통로 수), NS(갈림길 수), T(보물의 위치)가 공백으로 구분외어 주어진다.
다음 줄 부터는 NS개의 갈림길의 정보가 a b c 형태로 주어진다.
a번 길이 b와 c로 갈라진다는 정보이고 a는 b, c보다 입구에서 가깝다.
출력
보물로 가는 가장 짧은 단계 수와 그 통로를 한 줄에 하나씩 출력한다.
예제1
입력
1367
678
234
101112
8910
1213
456
출력
5
1
2
4
6
7
출처
USACO US Open 2009 Bronze