2874: 月老的难题

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:3 解决:2

题目描述

杜陵韦固,元和二年旅次宋城遇一老人倚布囊,坐于阶上,向月捡书。 固问所寻何书,答曰:“天下之婚牍耳。”又问囊中何物,答曰:“赤绳子耳。以系夫妻之足,及其生,则潜用相系,虽讎敌之家,贵贱悬隔,天涯从宦, 吴楚异乡,此绳一系,终不可逭。”
随着时代的发展,人口增加,月老神打算采用计算机帮祂完成“千里姻缘一线牵”任务
月老准备给$n$个女孩与$n$个男孩牵红线,成就一对对美好的姻缘。
现在,由于一些原因,部分男孩与女孩可能结成幸福的一家,部分可能不会结成幸福的家庭。
现在已知哪些男孩与哪些女孩如果结婚的话,可以结成幸福的家庭,月老准备促成尽可能多的幸福家庭,请你帮他找出最多可能促成的幸福家庭数量吧。
假设男孩们分别编号为$1$~$n$,女孩们也分别编号为$1$~$n$。

输入

第一行是一个整数$T$,表示测试数据的组数(1<=T<=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

提示

本题21~25输入数据较大(>=30MB),请使用较快的OI方式。


请使用快读
inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}