浮島
發布時間: June 27, 2024, 7:51 p.m. 最後更新時間: June 28, 2024, 7:52 a.m. 時間限制: 1000ms 記憶體限制: 128M
很久很久以前，在遙遠的銀河系，有一顆海洋星球
這顆星球除了廣闊的大海之外，僅有的少數陸地是由$a\times b$個浮島所組成的矩形
為了方便管理，這顆星球的領主將所有島嶼由左至右由上往下編號為$1$~$a\times b$
例如：$a=3,b=4$，則所有島嶼排列為
1 2 3 4
5 6 7 8
9 10 11 12
已知所有島嶼與其左上、右上、左下、右下之島嶼間皆有橋梁連通
例如：上例之6號島嶼與1、3、9、11號島嶼間皆有橋梁連通
另外，為了通勤方便，這顆星球的領主還額外建造了$m$座橋梁，每座橋梁連接兩座島嶼
請問：從1號島嶼走到最後1號島嶼最少須經過多少座橋？
（兩島嶼間需有橋梁才能通行，所有橋梁均可雙向通行）
第一行輸入三整數$a,b,m$
接下來$m$行，每行輸入兩正整數$x,y$，表示$x$號島嶼與$y$號島嶼間有橋梁連通
$1\le x,y\le a\times b\le 10^5，a,b,x,y\in N$
$0\le m\le 10^5，m\in Z$
輸出一整數$ans$，表示從1號島嶼走到最後1號島嶼最少須經過多少座橋
若無法走到最後1號島嶼則輸出-1
複製範例
3 4 3 1 8 3 10 8 10
4
複製範例
2 3 1 1 3
-1
複製範例
1 1 0
0
