← 返回题目列表

Codeforces · 346/D

D. 机器人控制

中文机器翻译题面 查看原题

机器人公司的老板是个残忍的人。他的座右铭是“前进或死亡!”。而这正是他公司的产品所做的。看看该公司的机器人在有向图中行走时的行为。这种行为被称为“机器人三定律”:

- 法则 1. 当机器人访问它已经访问过的图的顶点时,机器人将摧毁自己。
- 法则2。当机器人无路可走时(即当它到达出度为零的顶点时),机器人将会自我毁灭。
- 法则3。当机器人有多种移动方式时(即到达出度大于1的顶点时),机器人将随机移动。当然,机器人只能沿着图的有向边移动。

你能想象一个机器人会有这样的行为吗?这就是为什么它们会以很低的价格出售,只是为了那些缺钱的人,当然也包括mzry1992。 mzry1992有这样一个机器人,她想将它从有向图中的顶点s安全地移动到顶点t,而不会自毁。幸运的是,她可以在每个顶点向机器人发送特殊命令。如果机器人有多种移动方式,则特殊命令会显示机器人以哪种方式移动(以防止机器人根据定律 3 随机移动)。当机器人到达顶点 t 时,mzry1992 立即将其从图表中删除。所以你可以看到,只要存在从 s 到 t 的路径,她总能找到到达目标的方法(无论顶点 t 的出度是否为 0)。

样本 2

然而,发送订单的成本很高,因此您的任务是找到 mzry1992 在最坏情况下需要发送的最小订单数量。请注意,mzry1992 可以在机器人在图表上行走时向其发出命令。查看第一个示例以澄清该部分问题。

输入

第一行包含两个整数 n (1 ≤ n ≤ 106) — 图的顶点数,m (1 ≤ m ≤ 106) — 边数。接下来是 m 行,每行有两个整数 ui 和 vi (1 ≤ ui, vi ≤ n; vi ≠ ui),这些整数表示从顶点 ui 到顶点 vi 存在一条有向边。最后一行包含两个整数 s 和 t (1 ≤ s, t ≤ n)。

保证不存在重边和自环。

输出

如果有办法达到目标,则打印最坏情况下所需的最小订单数。否则,打印-1。

示例

输入 #1

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

输出 #1

1

输入 #2

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

输出 #2

1

注意

考虑第一个测试样本。最初,机器人位于顶点 1。因此,第一步,机器人可以前往顶点 2 或 3。无论机器人选择哪个顶点,mzry1992 都必须向机器人发出命令。这个命令是去顶点4。如果mzry1992没有在顶点2或3处给机器人发出命令,机器人可以根据定律3选择“坏”的出边(返回到顶点1)。所以,答案是1。