J |
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 (
President of Waterland wants to
spend his upcoming vacation in
ESF sends a group of teams in all
routes from
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.
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.
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