题目描述

知名汽车公司 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

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

-1

输入输出样例 #3

输入 #3

8 11
1 2
2 1
2 3
3 4
3 8
4 1
4 5
5 6
5 7
6 7
6 8
1 8

输出 #3

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$	无额外限制