西元 3110 年,大多數的陸地已經陷入水中,只剩下少數的島嶼。水島是由許多小島嶼所組成,所有小島嶼間藉由隧道連接,每個隧道兩端確切只有 2 個島嶼。
水島總統想要去 Yablonoi 島度假,精英安全部隊必須要護送總統從 Kurai 島到 Yablonoi 島,他們必須選擇安全的隧道來前進。在每種可能路徑中,每條隧道都只能經過一次。
安全部隊每次派出有很多小隊一起出發,嘗試每種不同的路徑,每經過島嶼時,會留下一個小隊駐守,每次都只會剩下一個小隊抵達 Yablonoi 島,而一座小島可能會有多個小隊來自於不同次出發的。
現在安全部隊的負責人要計算總共派發出的小隊個數,並且計算有多少個小隊抵達目的地。
Input
測資第一行有一個整數 N (N < 40),表示測資組數。
對於每組測資,第一行會有兩個整數 L, T (2 <= L <= 5000, 0 <= T <= 5*L),分別表示島嶼個數,以及安全隧道的個數。
接下來會有 T 行,每行上有兩個整數 x, y (1 <= x, y <= L),表示有一條有向隧道從 x 到 y。對於任兩個島嶼間最多有一條隧道連接,而島嶼編號 1 為 Kurai 島,島與編號 L 為 Yablonoi 島。
對於每組測資,第一行會有兩個整數 L, T (2 <= L <= 5000, 0 <= T <= 5*L),分別表示島嶼個數,以及安全隧道的個數。
接下來會有 T 行,每行上有兩個整數 x, y (1 <= x, y <= L),表示有一條有向隧道從 x 到 y。對於任兩個島嶼間最多有一條隧道連接,而島嶼編號 1 為 Kurai 島,島與編號 L 為 Yablonoi 島。
Output
對於每組測資,輸出測資組編號,以及兩個整數 S, D,分別表示總共需要的小隊數,以及最後抵達目的地的小隊總數。
只需打印出 mod 100000 的結果即可。
只需打印出 mod 100000 的結果即可。
Sample Input Output for Sample Input
3
2 1
1 2
4 4
1 2
1 3
2 4
3 4
4 3
1 2
2 3
3 4
|
Case 1: 1 1
Case 2: 4 2
Case 3: 3 1
|
沒有留言:
張貼留言