J

Water Land

Input: Standard Input

Output: Standard Output

 

The year 3110. Most of the lands have disappeared under water, leaving many small islands. Waterland is a peaceful country consisting of many such islands. All islands in Waterland are connected by tunnels. Each tunnel connects exactly two islands. Tunnels are very expensive to build, so WRTA (Waterland Road and Tunnel Authorities) tries to keep the number of tunnels as low as possible. (You may be wondering why not just use air transport! Air transport can no longer be used due to terrible weather condition.)

 

President of Waterland wants to spend his upcoming vacation in Yablonoi Island, after the long and tedious hours of work at office (Kurai Island). The Elite Security Force (ESF) of Waterland, who is responsible for president’s security, always takes precautions before his journey. They have selected some of the safe tunnels from Kurai Island to Yablonoi island. Safe tunnels are chosen in such a way that if anyone starts to travel from Kuriai island to Yablonoi Island, it is not possible to visit any island twice with any possible route.

 

ESF sends a group of teams in all routes from Kurai Island to Yablonoi Island. Each group of teams drops one team at each island (except Kuroi – the president’s office) on their route and moves on. At the end, for each route, only one team from each group will reach in Yablonoi Island. Therefore, one island may contain multiple teams from different groups. Now the Chief of ESF asks you to calculate the total number of teams required for the whole process and the number of teams reached at destination (Yablonoi Island).

 

Input

First line of the input represents the number of test cases N (N≤40). Each test case starts with a line containing 2 numbers L and T, where L represents the number of island (2 ≤ L ≤ 5000) in that country and T (0≤T≤5*L) represents the number of safe tunnels. After that, there will be T lines with two numbers: x and y (1≤ x,y ≤ L) representing the tunnel between island x and island y. All of these tunnels are one way (from x to y) on that day (for the sake of president’s safety). There will be at most one tunnel between any two islands. Consider the “island 1” as Kurai island and “island L” as Yablonoi island.

 

Output

For each test case, print the case number first followed by two numbers, S and D where S represents the number of teams that is required by ESF for the whole process and D represents the number of teams that reached in the meeting place after the whole operation. Print both numbers (S and D) in modulo 1,00,000.

 

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

Problem setter: Syed Monowar Hossain, Special Thanks: Md. Arifuzzaman Arif