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)，表示有一條有向隧道從 x 到 y。對於任兩個島嶼間最多有一條隧道連接，而島嶼編號 1 為 Kurai 島，島與編號 L 為 Yablonoi 島。

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