题目描述

知名汽車公司 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$ 的路徑。

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