题目描述

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

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

2

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

-1

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

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)$。
• 輸入的數皆為整數。

評分說明

本題共有四組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。