보물 동굴

베시의 할아버지는 해적이었고, 황금 약탈품으로 가득한 커다란 보물 상자를 모았습니다. 그는 그 보물 상자를 어느 동굴에 숨겼는데, 최근 베시가 파머 존의 땅에서 바로 그 동굴을 발견했습니다! 동굴 입구 바로 안쪽에서 베시는 보물까지 가는 길을 알려 주는 지도를 찾았습니다.

동굴에는 $1$번부터 $P$번까지 번호가 매겨진 $P$개의 통로가 있습니다 ($3 \le P \le 5000$). 입구는 $1$번 통로이며, 보물은 도달 가능한 어떤 통로 $T$ ($2 \le T \le P$)에 있고 그 번호가 주어집니다. 모든 통로의 길이는 거의 같습니다. 각 통로는 갈림길로 이어지고, 그 갈림길에서 아직 탐험하지 않은 번호 매겨진 통로들이 호기심 많은 소를 더 깊은 지하로 이끕니다. 어떤 통로도 두 개 이상의 통로에서 갈라져 나오지 않으며, 지도에는 총 $NS$개의 갈림이 있습니다 ($1 \le NS \le 5000$).

베시는 보물이 입구에서 얼마나 멀리 있는지, 그리고 보물까지 가려면 어떤 번호의 통로를 지나야 하는지를 모두 알고 싶어 합니다.

아래에 동굴을 나타낸 도식이 있습니다. 각 통로 번호는 그것이 가리키는 통로 옆에 적혀 있습니다. 이 예시에서 보물은 $7$번 통로 끝에 있습니다:

                   3/
                   /
                  +
                 / \   /5
               2/  4\ /
           1   /     +
          ----+      6\   #7    /11
               \       \ /     /
              13\       +     +
                        8\ 10/ \
                          \ /   \12
                           +
                           9\
                             \

이 경우 베시는 보물에 도달하기 위해 통로 $1, 2, 4, 6, 7$을 지나야 하며, 이동한 총 거리는 $5$입니다 (거리는 곧 지나간 통로의 개수입니다).

각 갈림은 통로 번호 $N$ ($1 \le N \le P$)과 그 통로에서 갈라져 나오는 두 통로 $B_1, B_2$ ($1 \le B_1 \le P$, $1 \le B_2 \le P$)로 주어집니다. 입력에는 $1$번 통로와 그 두 갈래(위 예시에서는 통로 $2$와 $13$)를 나타내는 줄이 반드시 포함됩니다. 마찬가지로 $8$번 통로에도 두 갈래 $9$와 $10$이 있습니다.

베시가 보물까지 가는 길을 알려 주세요.

• 첫째 줄: 공백으로 구분된 세 정수 $P$, $NS$, $T$
• $2$번째 줄부터 $NS+1$번째 줄까지: 각 줄에 공백으로 구분된 세 정수 $N$, $B_1$, $B_2$

• 첫째 줄: 입구에서 보물까지의 거리 $D$
• $2$번째 줄부터 $D+1$번째 줄까지: 입구에서 보물까지 순서대로, 베시가 지나는 통로 번호를 한 줄에 하나씩 출력합니다.