As vacas foram enviadas ao espaço para adquirir uma nova máquina de ordenha para seu celeiro. Voam por um aglomerado de estrelas contendo $N$ planetas ($1 \le N \le 50{,}000$), cada um com um posto comercial.

Descobriram quais dos $K$ tipos de objetos ($1 \le K \le 1{,}000$), numerados $1..K$, cada planeta deseja e o que oferece. Nenhum tem moeda: usam escambo, e cada parte troca exatamente um objeto (presumivelmente de tipos diferentes).

Partem da Terra com um recipiente de feno de qualidade (objeto 1) e desejam uma máquina de ordenha (objeto $K$). Encontre a melhor sequência de trocas nos planetas para obter o objeto $K$. Se for impossível, imprima -1.

Entrada

• Linha 1: dois inteiros $N$ e $K$ separados por espaço.
• Linhas $2..N+1$: a linha $i+1$ contém dois inteiros $a_i$ e $b_i$ separados por espaço, os produtos de troca do planeta $i$. Ele dá o objeto $b_i$ para receber o $a_i$.

Saída

• Linha 1: o menor número de trocas para obter a máquina, objeto $K$, mais um (ou -1 se não puderem obter o objeto $K$).
• Linhas $2..T+1$: lista dos objetos que as vacas possuem na ordem das trocas.

Exemplos

Entrada 1

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

Saída 1

4
1
3
2
5

Explicação

Detalhes da saída

Possuem 4 objetos no total: primeiro trocam 1 por 3, depois 3 por 2 e depois 2 por 5.

Créditos do problema: Coaches, 2004