400910: GYM100283 D Bakkar And The Algorithm Quiz

Many years have passed … Bakkar is now a computer science student and its his third year at college. This year they study an Algorithm course where they enjoy learning new algorithmic and problem solving techniques. The course instructor loves to give them programming puzzles to help him discover talented and hardworking students.

Moreover the instructor is a chess maniac; he loves to make programming puzzles about chess. Today the instructor told the students that he is going to make a quiz with a bonus value of 10 points (which is very high by the way). The students were very excited and motivated to know the problem and of course to be able to solve it to get the bonus ;).

The problem description is as follows:

Unlike the normal 8 by 8 chessboard, this game is played on a N rows by M columns chessboard. You are allowed to place some Rooks on the chessboard. A rook placed on the cell (i,j) will attack all the cells in the ith row and jth column.

You really hate some cells on this chessboard, and you want to super-attack these cells by rooks. For a cell to be super-attacked, both of it's row and column must be attacked by rooks. A rook super-attacks the cell directly beneath it.

The goal of the game is to use the minimum number of rooks to super-attack all of the cells you hate. Since you thought that task is too easy, you also decided to count the number of different ways to solve this game with the minimum number of rooks. Rooks are identical, and two ways are considered different if a position has a rook in one way but is empty in the other. Since this number can be very large, you only need to calculate it mod 1,000,000,007.

Interesting problem isn't it?!! Well Bakkar is very excited and already has a solution in his mind for the problem.

Ok; the time is over now for the quiz and Bakkar is claiming that he has solved the problem successfully and you as a Teaching Assistant in the course musr prepare a program to validate the students' solutions. Let's validate Bakkar's solution by running some test cases against his solution and recording it for evaluation by the validator.

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  100). Followed by T test cases, each test case starts with a line containing three integers separated by a single space N, M and K (1  ≤  N,M  ≤  10⁹ , 1  ≤  K  ≤  10³), representing the number of rows and columns in the chess board, and the number of cells you hate, respectively. The next K lines represent the cells you hate. Each line contains two integers separated by a single space r and c (1  ≤  r  ≤  N , 1  ≤  c  ≤  M) which represent the represent the row and column of a cell you hate, respectively. All the cells will be distinct.

For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed 2 integers, space separated, representing the minimum number of rooks needed and the number of ways to place those rooks that Bakkar's solution outputted.

2
4 5 2
1 2
1 3
3 4 3
1 1
2 2
3 3

Case 1: 2 7
Case 2: 3 6