2013年9月18日 星期三

11655 - Waterland

西元 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),表示有一條有向隧道從 xy。對於任兩個島嶼間最多有一條隧道連接,而島嶼編號 1 為 Kurai 島,島與編號 LYablonoi 島。

Output

對於每組測資,輸出測資組編號,以及兩個整數 S, D,分別表示總共需要的小隊數,以及最後抵達目的地的小隊總數。

只需打印出 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