Le mucche sono state inviate nello spazio per acquistare una nuova mungitrice per la stalla. Volano attraverso un ammasso di stelle con $N$ pianeti ($1 \le N \le 50{,}000$), ciascuno con un punto commerciale.

Hanno scoperto quali dei $K$ tipi di oggetti ($1 \le K \le 1{,}000$), numerati $1..K$, desidera ogni pianeta e cosa offre. Nessuno ha moneta: usano il baratto e ogni parte scambia esattamente un oggetto (presumibilmente di tipi diversi).

Partono dalla Terra con un contenitore di fieno di qualità (oggetto 1) e desiderano una mungitrice (oggetto $K$). Trovate la migliore sequenza di scambi sui pianeti per ottenere l’oggetto $K$. Se impossibile, stampate -1.

Input

• Riga 1: due interi $N$ e $K$ separati da spazio.
• Righe $2..N+1$: la riga $i+1$ contiene due interi $a_i$ e $b_i$ separati da spazio, i prodotti di scambio del pianeta $i$. Offre l’oggetto $b_i$ per ricevere $a_i$.

Output

• Riga 1: il numero minimo di scambi per ottenere la macchina, oggetto $K$, più uno (o -1 se non possono ottenere $K$).
• Righe $2..T+1$: gli oggetti posseduti dalle mucche nell’ordine degli scambi.

Esempi

Input 1

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

Output 1

4
1
3
2
5

Spiegazione

Dettagli dell’uscita

Possiedono 4 oggetti in totale: prima scambiano 1 con 3, poi 3 con 2 e poi 2 con 5.

Autori del problema: Coaches, 2004