Bò được cử đi vũ trụ để kiếm máy vắt sữa mới cho chuồng. Chúng bay qua cụm sao có $N$ hành tinh ($1 \le N \le 50{,}000$), mỗi nơi có điểm giao dịch.

Chúng biết mỗi hành tinh muốn loại nào trong $K$ loại vật phẩm ($1 \le K \le 1{,}000$), đánh số $1..K$, và có gì để đổi. Không hành tinh nào có tiền tệ, nên dùng trao đổi hàng: mỗi bên đổi đúng một vật phẩm (có lẽ khác loại).

Bò rời Trái Đất với hộp cỏ khô chất lượng cao (vật phẩm 1) và muốn máy vắt sữa (vật phẩm $K$). Tìm chuỗi trao đổi tốt nhất trên các hành tinh để có vật phẩm $K$. Nếu không thể, in -1.

Dữ liệu vào

• Dòng 1: hai số nguyên $N$ và $K$ cách nhau bởi khoảng trắng.
• Dòng $2..N+1$: dòng $i+1$ chứa hai số nguyên $a_i$, $b_i$ cách nhau bởi khoảng trắng, là vật phẩm giao dịch của hành tinh $i$. Nó đưa $b_i$ để nhận $a_i$.

Dữ liệu ra

• Dòng 1: số lần trao đổi ít nhất để có máy, vật phẩm $K$, cộng một (hoặc -1 nếu không có được $K$).
• Dòng $2..T+1$: danh sách vật phẩm bò sở hữu theo thứ tự trao đổi.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4
1
3
2
5

Ghi chú

Chi tiết đầu ra

Bò sở hữu tổng cộng 4 vật phẩm: đầu tiên đổi 1 lấy 3, sau đó 3 lấy 2, rồi 2 lấy 5.

Tác giả bài toán: Coaches, 2004