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$ | 無額外限制 |