Description
You might think that Earth is the only planet where life is going on, but it is not true. About 880,228 light years away from Earth, there is a big planet, Haden, where another kind of human beings exists.
Unfortunately, there is another creature living on Haden: a dragon. This dragon attacks villages to find food whenever it gets hungry. People are getting sick of being attacked and being harmed. Now, they decided to select one strong dragon slayer to kill the dragon.
As one of human beings living on Haden, you've seen a lot of disasters caused by the dragon and you want to become a good dragon slayer. Here's the first task that you are given:
You have an n by n chess board where n is even. This chess board looks regular except that it has a couple of red cells and yellow cells, not only black and/or white. You are going to place many of white rooks and/or black rooks on the chess board. Here are the rules:
Each cell has a color of black, white, yellow, or red
You cannot place any rooks on yellow cells
You must place one rook (either black or white, your choice) on each red cell
You may not place a black rook on a black cell
You may not place a white rook on a white cell
There should be no pair of two rooks with the same color that can attack each other. If two rooks with the same color are placed on the same row OR same column, they can attack each other.
You must maximize the total number of rooks that you place on the board
Let's take a look at following examples.
On the left 6 by 6 chess board, you can place 6 black rooks and 6 white rooks as indicated as small circles. On the right board, it is a bit more complicated due to two red cells, but you can safely place the same number of rooks here, too. Since you can never place more than 2n rooks (n white rooks and n black rooks), this is the maximum number of rooks that you can place without violating any rules. Note that both examples don't have any yellow cells. Let's write a program to solve this task so that you can advance to the next round!
Input
A test set can have several test cases, and the number of test cases is given at the first line. Each test case starts with three integers, n, m, and k where n tells you the size of a chess board, m is the number of red cells on the board, and k is the number of yellow cells. Each of following m lines contains two integers (row number and column number, 0-based), representing a red cell on the board. Then, each of following k lines contains two integers, representing a yellow cell on the board. See the sample input for clarification. You may assume that any cell cannot be both yellow and red and that the same cell is not given more than once. For each test case, n, m, and k do not exceed 40, 10, and 1600, respectively.
Output
For each test case, output only one integer, the maximum possible number of rooks that you can place. If such placement doesn't exist, output 0.
Sample Input
4
6 0 0
6 2 0
2 1
5 5
2 0 2
0 0
0 1
2 3 1
0 0
0 1
1 1
1 0
Sample Output
12
12
2
3
http://acm.tzc.edu.cn/acmhome/vProblemList.do?method=problemdetail&oj=POJ&pid=3319
