问题 22069 --搭配问题

22069: 搭配问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 21  解决: 5
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][2236kb]

题目描述

小明班上周末准备组织去公共场所进行义务劳动,小明作为班长要考虑同学的组织问题。

他想,男女搭配,干活不累。如果把班上的同学男女一组两两搭配起来,干起活来肯定轻松加愉快。

虽然班上男女比例很神奇的为1:1,但是小明知道,女生只愿意和一部分男生搭配在一起。

那么,有没有一种办法,既让女生都和自己愿意的男生进行搭配,同时搭配的数量又达到最大呢?


现在已知哪些女生愿意和哪些男生搭配,请你帮助小明解决这个问题吧。

输入

第一行是一个整数K,表示测试数据的组数(1<=K<=400)

每组测试数据的第一行有两个整数n,K,其中男生的人数与女生的人数都是n。(n<=500,K<=10 000)

随后的K行,每行有两个整数i、j,表示第i个女生愿意和第j个男生进行搭配。(1<=i,j<=n)

输出

对每组测试数据,输出最多可能促成的搭配数量

样例输入

1
3 4
1 1
1 3
2 2
3 2

样例输出

2

提示

来源

[提交][状态]