文理学院程序设计在线练习


挑选班干部

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 49   Accepted Submission(s): 15
Problem Description

班干部评选工作正在开始,候选人中包括男生M个和女生F个。而且已经分别进行了编号。即男生1~M号,女生1~F。候选人之外的其他N个学生参与投票。

不过,这个班级学生对班干部的投票规则非常特殊:投票学生每人一张选票,且要求每张选票的正面和反面分别写上候选人(规定必须为1男1女)的编号,其中正面写上他认为最合适的候选人的代号,反面写上他认为最不合适的候选人的代号。

而且这个班级的投票学生还非常有个性,一旦他 认为最合适的人未能当选 或者 他认为最不合适的人当选 班干部的话,这个学生将用退学的方式表示抗议。

例如:在Sample Input的第一组测试中,若要挽留第1个投票学生,必须满足男候选1号入选 并且 女候选1号不入选。

在得到全部N张选票后,如何进行班干部的取舍让班主任非常为难,尽管他能够全权处理班干部的任免,但毕竟众口难调。

现在请你帮忙确定一下,假设能做出最佳选择的话,最多能挽留多少投票学生不退学。

注意,这里假设最终当选的班干部总人数没有限制。

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T行测试数据。
每组测试的第一行包括3个整数m,f,n (1 <= M, F <= 100 , 0 <= N <=500), 注意:N可能为0。
然后是N行,代表N个学生递交的选票信息,每行2个编号,依次代表写在正面的编号,和写在反面的编号。
编号一定由M或F打头,后接数字序号,代表合适或不合适的男生或女生编号。例如:M42就代表第42号男候选者,而F2则代表第2号女候选者。

Output

对于每组测试,输出最多能挽留的投票学生数量。

Sample Input
3
1 1 2
M1 F1
F1 M1
1 1 2
M1 F1
M1 F1
1 2 4
M1 F1
M1 F1
M1 F2
F2 M1
Sample Output
1
2
3
Hint

说明:
对于第1组测试,保留1号男候选或者保留1号女候选,均可以挽留1个投票学生。
对于第2组测试,保留1号男候选,可以挽留全部2个投票学生。
对于第3组测试,保留1号男候选,除了第4个投票学生退学外,其余3个投票学生可以挽留。

Source

2011校计算机技能竞赛