P11904 [NHSPC 2023] C. 与自动辅助驾驶畅游世界

知名汽车公司 EWM 在自家的汽车上安装了最新的自动驾驶辅助 (auto co-pilot) 技术，让汽车在驾驶员没有给出明确指令的情况下，也能依据 AI 做出的决策前进。身为车主的小明，自然开始计划使用这款具备自动驾驶辅助技术的汽车以畅游世界。 这个世界可以看作一张有向图 (directed graph) $G$，其中 $G$ 上的点 $s$ 为小明目前的位置，点 $t$ 为小明欲到达的终点。为了兼顾行车安全，EWM 的汽车在 $G$ 上的行进期间，必须遵循有向边 (directed edge) 的方向前进，不能逆向行驶；在此前提下，无论所在的位置为何，AI 都会从所有可以前进的方向中，均匀随机地 (uniformly random) 选择一个方向前进。举例来说，若汽车目前在点 $a$，而点 $a$ 有三条向外的边，分别连到点 $b, c, d$，此时 AI 辅助驾驶会从点 $b, c, d$ 中，以概率各为 $1/3$ 的方式选出一个前进。 为了使驾驶员能控制汽车往他/她希望的方向前进，EWM 公司提供了以下的机制：在 AI 做出决策前，驾驶员可以支付 $1$ 枚 EWM 公司发行的代币，让 AI 选择驾驶员希望的方向。以上一个例子为例，若小明在点 $a$ 时不希望 AI 做随机选择，而是直接选择某个点（例如点 $b$）前进，那么他可以支付 $1$ 枚代币，控制 AI 直接选择走向点 $b$。请注意一次代币支付仅限使用于一次选择，亦即若汽车重新回到了同一个支付过代币的点，AI 并不会直接往上一次支付代币时指定的方向前进，而是会重新均匀随机地做出选择；如果驾驶员仍想指定汽车的前进方向，必须再次支付 $1$ 枚代币。 小明想要知道，他最少需要准备多少枚代币，才能保证在抵达终点 $t$ 前的任何时刻都存在一条从他的所在地抵达终点 $t$ 的路径。

> $n$ $m$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_m$ $v_m$ > $s$ $t$ * $n$ 代表 $G$ 的节点数。 * $m$ 代表 $G$ 的边数。 * $u_i, v_i$ 代表 $G$ 有一条边从 $u_i$ 有向连到 $v_i$。 * $s$ 代表小明目前的位置。 * $t$ 代表小明欲到达的终点。

如果小明有办法在支付一些代币后到达 $t$，请输出 > $\textrm{ans}$ 其中 $\textrm{ans}$ 代表最少需要支付的代币数。否则，输出 > $-1$

### 测试数据限制 * $1 \le n \le 3000$。 * $1 \le m \le 30000$。 * $1 \le u_i \le n$。 * $1 \le v_i \le n$。 * $1 \le s \le n$。 * $1 \le t \le n$。 * 对任意 $i, j \in \{1, 2, \ldots, m\}$，若 $i \ne j$，则 $(u_i, v_i) \ne (u_j, v_j)$。 * 输入的数皆为整数。 ### 评分说明 本题共有四组子任务，条件限制如下所示。 每一组可有一或多个测试数据，该组所有测试数据皆需答对才可获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | $4$ | $m = n-1$，且存在某个点 $r$ 满足从 $r$ 出发可以到达 $G$ 上的其他点 | | 2 | $24$ | $G$ 不包含任何环 (cycle) | | 3 | $31$ | $n \le 100, m \le 1000$ | | 4 | $41$ | 无额外限制 |