CF346D Robot Control

机器人公司的老板是个残忍的人。他的座右铭是：“前进，否则毁灭！”。他的公司生产的机器人也正是这样做的。请看看该公司机器人在有向图中行走时的行为。这种行为被称为“机器人三定律”： - 定律1：当机器人到达已经访问过的顶点时，它会自毁。 - 定律2：当机器人无路可走时（即到达出度为零的顶点），它会自毁。 - 定律3：当机器人有多条路可走时（即到达出度大于一的顶点），它会随机选择一条路前进。当然，机器人只能沿着图中的有向边移动。 你能想象这样的机器人吗？这正是它们售价非常低廉的原因，只卖给那些资金紧张的人，包括 mzry1992。mzry1992 拥有这样一个机器人，她希望能够把机器人从有向图中的顶点 $s$ 安全地移动到顶点 $t$，而不使其自毁。幸运的是，她可以在每个顶点给机器人发送特殊指令。一条特殊指令可以指定机器人在有多条选择时应该走哪一条边（用来阻止机器人依照定律3随机移动）。当机器人到达顶点 $t$ 时，mzry1992 会立即把它从图中拿下来。因此，只要从 $s$ 到 $t$ 有路径，无论 $t$ 的出度是否为零，她总能找到一种方式使机器人到达目标。 不过，发送指令是有代价的，你的任务是找出在最坏情况下，mzry1992 至少需要发送多少条指令。请注意，mzry1992 可以在机器人行进到某个顶点时再发送指令。请参考第一个样例以了解问题的具体情况。

第一行包含两个整数 $n$（$1 \leq n \leq 10^6$）——图中顶点的数量，以及 $m$（$1 \leq m \leq 10^6$）——边的数量。接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$；$v_i \neq u_i$），表示有一条从顶点 $u_i$ 指向顶点 $v_i$ 的有向边。最后一行包含两个整数 $s$ 和 $t$（$1 \leq s, t \leq n$）。 保证不存在重边和自环。

如果存在从 $s$ 到 $t$ 的路径，输出所需的最坏情况下的最小指令数；否则输出 $-1$。

考虑第一个测试样例。最开始机器人在顶点 1 上，因此它的第一步可以走向顶点 2 或 3。无论机器人选择哪个顶点，mzry1992 都必须给机器人发送一条指令。这条指令是让机器人走向顶点 4。如果 mzry1992 在顶点 2 或 3 不下指令，机器人根据定律3可能会选择“错误”的边（返回到顶点 1）。所以答案是 1。 由 ChatGPT 5 翻译