Treasure Cave

Bessie's grandfather was a pirate who amassed a great chest of golden plunder. He hid the treasure chest in a cave that Bessie has just discovered on Farmer John's land! Just inside the cave's entrance she found a map showing how to reach the treasure.

The cave has $P$ passages ($3 \le P \le 5000$), numbered $1$ through $P$. The entrance is passage $1$; the treasure lies in some reachable passage $T$ ($2 \le T \le P$), whose number is given. All passages are roughly the same length. Each passage leads to a split, where previously unexplored numbered passages take the curious cow deeper underground. No passage branches off from more than one passage, and the map contains $NS$ splits in total ($1 \le NS \le 5000$).

Bessie wants to know both how far the treasure is from the entrance and which passage numbers she must take to reach it.

Below is a schematic drawing of a cave. Each passage number is written next to the passage it names. In this example the treasure lies at the end of passage $7$:

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

Here Bessie must traverse passages $1, 2, 4, 6, 7$ to reach the treasure, for a total distance of $5$ (the distance is simply the number of passages traversed).

Each split is given as a passage number $N$ ($1 \le N \le P$) together with the two passages $B_1, B_2$ ($1 \le B_1 \le P$, $1 \le B_2 \le P$) that branch off from it. The input always includes the line for passage $1$ and its two branches (passages $2$ and $13$ in the example); likewise, passage $8$ has the two branches $9$ and $10$.

Tell Bessie how to reach the treasure.

• Line 1: three space-separated integers $P$, $NS$, and $T$
• Lines 2 to $NS+1$: each line contains three space-separated integers $N$, $B_1$, and $B_2$

• Line 1: the distance $D$ from the entrance to the treasure
• Lines 2 to $D+1$: the passage numbers Bessie takes to reach the treasure, in order from the entrance, one per line.