问题 q: 精明的老板

问题 q: 精明的老板

时间限制: 1 Sec  内存限制: 64 MB
提交: 28  解决: 6
[提交][状态][讨论版][命题人:]

题目描述

我们经常会听到一句话:“男女搭配,干活不累。”精明的老板经过观察发现,两个男女推销员搭配工作,业务量明显高于其他人。然而并不是任何两个男女推销员都可以合作默契的,如果有的男女推销员本身有矛盾,就无法一起工作。老板了解每个员工的配合情况后,可以设计一个算法找出最佳的推销员配对方案,使每天派出的推销员最多,从而获得最大的效益。

输入

第一行是一个整型数C(C<100)表示共有C组测试数据。
每组测试数据第一行输入女推销员人数m和男推销员人数n(1<=m,n<=100)。
接下来输入可以配合的女推销员编号u和男推销员编号v(两个都为-1结束)(1<=u<=100,u<v<=200)。

输出

对于每一组输入,输出最大配对数。
每组的输出占一行。

样例输入

2
5 7
1 6
1 8
2 7
2 8
2 11
3 7
3 9
3 10
4 12
4 9
5 10
-1 -1
4 5
1 5
1 6
2 7
3 8
3 9
4 7
-1 -1

样例输出

5
3

提示

[提交][状态]