奶牛们接到太空任务，要为牛棚获取一台新挤奶机。她们正在穿过一个包含 $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