//两道大水……哦不 两道结论题
结论：二部图的最小覆盖数=二部图的最大匹配数
有向图的最小覆盖数=节点数-二部图的最大匹配数
//hdu 1150
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string> using namespace std; int n,m,k;
int f[][];
int link[];
bool adj[];
bool used[]; bool work(int x){
for (int i=;i<m;i++){
if (f[x][i] && adj[i]==false){
adj[i]=true;
if (!used[i] || work(link[i])){
link[i]=x;
used[i]=;
//printf("%d %d\n",x,i);
return true;
}
}
}
return false;
} int main(){
while (scanf("%d%d%d",&n,&m,&k)==){
memset(f,,sizeof(f));
memset(used,,sizeof(used));
for (int i=;i<k;i++){
int x,y,z;
scanf("%d%d%d",&z,&x,&y);
if (x!= && y!=){
f[x][y]=;
}
}
int ans=;
for (int i=;i<n;i++){
memset(adj,,sizeof(adj));
if (work(i)) ans++;
}
//for (int i=1;i<m;i++) printf("%d %d\n",i,link[i]);
printf("%d\n",ans);
}
return ;
}
/*
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
*/
//hdu 1151
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string> using namespace std; int T;
int n,m;
bool f[][];
int link[];
bool adj[];
bool used[]; bool work(int x){
for (int i=;i<=n;i++){
if (f[x][i] && !adj[i]){
adj[i]=;
if (!used[i] || work(i)){
link[i]=x;
used[i]=;
return true;
}
}
}
return false;
} int main(){
scanf("%d",&T);
for (int cas=;cas<=T;cas++){
memset(used,,sizeof(used));
memset(link,,sizeof(link));
memset(f,,sizeof(f));
scanf("%d",&n);
scanf("%d",&m);
for (int i=;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
f[x][y]=;
}
int ans=n;
for (int i=;i<=n;i++){
memset(adj,,sizeof(adj));
if (work(i)) ans--;
}
printf("%d\n",ans);
}
return ;
}
/*
2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3
*/