Krowy wysłano w kosmos po nową dojarkę do obory. Lecą przez gromadę gwiazd zawierającą $N$ planet ($1 \le N \le 50{,}000$), każda z punktem handlowym.

Ustaliły, których z $K$ rodzajów przedmiotów ($1 \le K \le 1{,}000$), numerowanych $1..K$, chce każda planeta i co oferuje. Żadna nie ma waluty, więc stosują barter: każda strona wymienia dokładnie jeden przedmiot (zapewne różnych rodzajów).

Krowy startują z Ziemi z pojemnikiem dobrego siana (przedmiot 1) i chcą dojarkę (przedmiot $K$). Znajdź najlepszą serię wymian na planetach, aby zdobyć $K$. Jeśli to niemożliwe, wypisz -1.

Wejście

• Wiersz 1: dwie liczby całkowite $N$ i $K$ oddzielone spacją.
• Wiersze $2..N+1$: wiersz $i+1$ zawiera liczby całkowite $a_i$ i $b_i$ oddzielone spacją, produkty wymiany planety $i$. Odda przedmiot $b_i$ za przedmiot $a_i$.

Wyjście

• Wiersz 1: minimalna liczba wymian potrzebnych do dojarki, przedmiotu $K$, plus jeden (lub -1, jeśli nie mogą zdobyć $K$).
• Wiersze $2..T+1$: lista posiadanych przedmiotów w kolejności wymian.

Przykład

Wejście 1

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

Wyjście 1

4
1
3
2
5

Uwagi

Objaśnienie wyjścia

Posiadają łącznie 4 przedmioty: najpierw wymieniają 1 na 3, potem 3 na 2, potem 2 na 5.

Autorzy zadania: Coaches, 2004