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)
= (23)/2 + (23)/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