The Sorting Hat

Dripping wet after the boat ride across the lake owing to a few minor mishaps, (the

Squid was a light sleeper), the little witches and wizards have arrived safe and sound

at the castle of Hogwarts. They are ushered into the Great Hall by Professor

McGonagall, and they are about to be sorted into houses by the Sorting Hat.

Over the years, the Sorting Hat has mastered a technique that it follows while sorting

the children into houses. It first considers the child’s own preference, and will not allot

any little witch or wizard a house it does not want to be part of. Additionally, the Hat

understands that the total maintenance costs of the houses must be reduced as much

as possible (the rent being too damn high). The maintenance cost of any house i is

equal to ni (ni + 1) / 2, where ni is the number of students in house i. Simply put, the

hat seeks to minimize the total cost incurred by all the houses together, while also

respecting each individual child’s wishes.

What is the minimum possible total maintenance cost that can be achieved if the

sorting hat classifies the children optimally?

Input Format

The first line contains integer t<=5, the number of test cases. It is followed by t test

cases. The first line of each test case contains 2 space separated integers n and m -

the number of children and the number of houses respectively (n>=m). The second

line contains an integer e, denoting the total number of choices given by all students.

Then e lines follow, each containing 2 space separated integers i and j, implying that

house j is acceptable to the ith child.

Note: The children and the houses are numbered 1…n and 1…m respectively.

Output Format

For each test case, output a single integer, which represents the minimum possible

maintenance cost of the houses.

Constraints

n <= 250

e <= 1000

Sample Input

2

6 3

15

1 2

2 2

3 1

4 2

5 3

6 2

2 1

2 3

1 1

5 2

3 3

4 1

1 3

4 3

6 1

5 5

20

1 4

2 2

3 3

4 1

5 4

2 1

5 3

3 2

1 3

4 5

1 2

3 4

3 5

3 1

5 1

4 3

2 4

5 5

1 5

2 3

Sample Output

95

Explanation for the 1st test case:

The choices of a child for certain houses are represented by the edges.

Blue coloured edge represents the assignment of a child to a house.

Here, child 1 is assigned to House 2; child 2 is assigned to House 1 and so on.

Total Cost = Cost (House 1) + Cost (House 2)

- Cost (House 3)

= (2*3)/2 + (2*3)/2 + (2*3)/2

= 9

2nd Test case – every house gets 1 child since every child likes all houses. So the Cost

is 1 for each house.

Total cost = 1 + 1 + 1 + 1 + 1 = 5