Die Kühe wurden ins Weltall geschickt, um eine neue Melkmaschine für ihren Stall zu beschaffen. Sie fliegen durch einen Sternhaufen mit $N$ Planeten ($1 \le N \le 50{,}000$), jeweils mit einem Handelsposten.

Sie wissen, welche der $K$ Objektarten ($1 \le K \le 1{,}000$), nummeriert $1..K$, jeder Planet wünscht und was er anbietet. Kein Planet hat Geld entwickelt, daher herrscht Tauschhandel: Jede Seite tauscht genau ein Objekt (vermutlich verschiedener Arten).

Die Kühe starten von der Erde mit einem Behälter hochwertigen Heus (Objekt 1) und wollen eine Melkmaschine (Objekt $K$). Finde die beste Folge von Tauschgeschäften auf den Planeten, um Objekt $K$ zu bekommen. Falls unmöglich, gib -1 aus.

Eingabe

• Zeile 1: zwei durch Leerzeichen getrennte ganze Zahlen $N$ und $K$.
• Zeilen $2..N+1$: Zeile $i+1$ enthält zwei durch Leerzeichen getrennte ganze Zahlen $a_i$ und $b_i$, die Tauschprodukte von Planet $i$. Er gibt Objekt $b_i$ gegen Objekt $a_i$.

Ausgabe

• Zeile 1: die minimale Anzahl Tausche zur Melkmaschine, Objekt $K$, plus eins (oder -1, wenn Objekt $K$ unerreichbar ist).
• Zeilen $2..T+1$: die Objekte im Besitz der Kühe in der Reihenfolge der Tausche.

Beispiele

Eingabe 1

6 5
1 3
3 2
2 3
3 1
2 5
5 4

Ausgabe 1

4
1
3
2
5

Hinweis

Erläuterung der Ausgabe

Sie besitzen insgesamt 4 Objekte: erst tauschen sie 1 gegen 3, dann 3 gegen 2 und dann 2 gegen 5.

Aufgabenautoren: Coaches, 2004