Problem : 262 - Crocodile

當考古學家Benjamas 調查一個神祕的鱷魚地下城市後，她想立刻逃離這個城市。這個城市有N 個密室，同時有M 個雙向的通道，沒有兩個通道會連接同一對密室，且通過每個通道的時間不盡相同。這N 個密室中，只有K 個密室有出口可以逃出去。Benjamas 從密室0 開始逃跑，並想盡快到達一個有出口的密室。

這個城市的守護者想要阻止Benjamas 逃跑，他可以控制密門來擋住任一通道；也就是說，當新密門擋住某個通道時，前一個擋住通道的密門會被打開。

Benjamas 的情況如下：每次當她想從一個密室離開時，守護者可能會擋住連接這個密室的其中一個通道。Benjamas 就會從剩下暢通的通道中選擇其一進到另一個密室。當Benjamas進入某個通道後，守護者就不能阻擋這個通道，直到她到達另一個密室為止。當Benjamas到達另一個密室後，守護者可以再次選擇擋住連接此密室的其中一個通道（包含Benjamas剛經過的通道）。

Benjamas 想要事先找到一個簡單的逃跑計畫；更精確地說，她想要一些指令集告訴她在某個密室時該怎麼做。假設A 是一個有出口的密室，顯然的她不需要任何指令就可以逃離。

否則當她在密室A 時，相關指令必須是以下形式之一：

　•「如果到了密室 A，就選擇通往密室B 的通道。但是，如果這個通道被阻擋住了，就選擇通往密室C 的通道。」
　•「不用考慮密室 A，因為在這份逃跑計畫中根本不可能到達密室A。」

請注意，在某些情況下（例如讓Benjamas 繞圈圈），守護者可能讓Benjamas 無法逃出去。

如果有個逃跑計畫，不管守護者會怎麼行動，都能保證Benjamas 可以在有限的時間內到達有出口的密室，這就是一個好的逃跑計畫。對於一個好的逃跑計畫，若可以保證在 T 時間後，Benjamas 一定可以到達有出口的密室，且 T 為最小值，則我們稱這個好的逃跑計畫需要 T 時間。

Sample #1:

密室用圓圈表示，連接密室的通道用直線表示。有出口的密室用粗圓圈表示。Benjamas 一開始在密室0（有三角形標示處）。一個最佳的逃跑計畫如下：

　•如果到了密室 0，就選擇通往密室1 的通道；如果這個通道被擋住了，就選擇通往密室2 的通道。
　•如果到了密室 2，就選擇通往密室3 的通道；如果這個通道被擋住了，就選擇通往密室4 的通道。

在最壞的情況下，Benjamas 必須花費7 單位時間才能到達可逃出密室。

Sample #2:

最佳的逃跑計畫如下：

　•如果到了密室 0，就選擇通往密室3 的通道；如果這個通道被擋住了，就選擇通往密室2 的通道。
　•如果到了密室 2，就選擇通往密室3 的通道；如果這個通道被擋住了，就選擇通往密室1 的通道。
　•不用考慮密室 4，因為在這份逃跑計畫中根本不可能到達密室4。

在這計畫中， Benjamas 在14 單位時間內一定會到達有出口的密室。