奶牛們接到太空任務，要為牛棚取得一台新擠奶機。牠們正在穿過一個包含 $N$（$1 \le N \le 50{,}000$）顆行星的星團，每顆行星都有一個交易站。

奶牛們已確定星團中每顆行星想要哪種物品、又有哪些產品可交換。共有 $K$（$1 \le K \le 1{,}000$）種物品，編號為 $1..K$。沒有行星發展出貨幣，所以採用以物易物：每次交易雙方各交換恰好一件物品（大概是不同類型的）。

奶牛從地球出發，帶著一罐優質乾草（物品 1），希望取得新擠奶機（物品 $K$）。請幫助牠們找到在星團各行星上進行一系列交易以取得物品 $K$ 的最佳方式。若不可能，輸出 -1。

輸入格式

• 第 1 行：兩個用空格分隔的整數 $N$ 和 $K$。
• 第 $2..N+1$ 行：第 $i+1$ 行含兩個用空格分隔的整數 $a_i$ 和 $b_i$，分別是行星 $i$ 的交易物品。該行星願意交出物品 $b_i$ 來換取物品 $a_i$。

輸出格式

• 第 1 行：取得擠奶機（物品 $K$）所需的最少交易次數加一（若無法取得物品 $K$，則為 -1）。
• 第 $2..T+1$ 行：按交易順序列出奶牛持有的物品。

範例

輸入格式 1

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

輸出格式 1

4
1
3
2
5

說明

輸出說明

奶牛總共持有過 4 件物品：先用物品 1 換物品 3，再用物品 3 換物品 2，最後用物品 2 換物品 5。

題目作者：Coaches, 2004