本题没有可用的提交语言。

题目描述

奶牛被派往太空执行任务,为他们的谷仓购买一台新的挤奶机。它们飞过包含$N(1 <= N <= 50,000)$行星的恒星群,每颗行星都有一个交易站。

奶牛已经确定了$K(1 <= K <= 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项的挤奶机(或$-1$,如果奶牛无法获得物品$K$)。

*第2行。$T+1$:奶牛在交易序列中拥有的物品的有序列表。 输入数 1

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

输出数位 1

4
1
3
2
5

提示

OUTPUT 详细信息:

奶牛总共拥有4个对象:首先,它们将对象1交换为对象3,然后将对象3交换为对象2,然后对象2为对象5。 来源

USACO 2005年2月银牌