最
小
不
相
交
路
径
覆
盖
：
每
一
条
路
径
经
过
的
顶
点
各
不
相
同
.
最小不相交路径覆盖：每一条路径经过的顶点各不相同.
最
小
不
相
交
路
径
覆
盖
：
每
一
条
路
径
经
过
的
顶
点
各
不
相
同
.
跑
一
遍
最
大
流
，
找
出
最
大
匹
配
，
a
n
s
=
n
−
M
a
x
m
a
c
t
h
.
跑一遍最大流，找出最大匹配，ans=n-Max_{macth}.
跑
一
遍
最
大
流
，
找
出
最
大
匹
配
，
a
n
s
=
n
−
M
a
x
m
a
c
t
h
.
c
o
d
e
:
code:
c
o
d
e
:
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <bitset>
#include <vector>
#include<cstring>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
typedef unsigned long long ull;
#define Ios() ios::sync_with_stdio(false);
inline int read(){int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
const int N = 3e6+5;
const int maxn = 1e4+10;
int head[maxn],tot;
struct E{
int to,next,val;
}e[N];
class Max_Flow
{
public:
int s,t;
int tot,head[maxn],dep[maxn],cur[maxn];
Max_Flow(){tot=0;memset(head,-1,sizeof(head));}
void clear(){tot=0;memset(head,-1,sizeof(head));}
void add_e(int u,int v,int w){
e[tot].to=v,e[tot].next=head[u],e[tot].val=w;
head[u]=tot++;
e[tot].to=u,e[tot].next=head[v],e[tot].val=0;
head[v]=tot++;
}
bool bfs(int S,int T){
for(int i=0;i<maxn;i++) dep[i]=0,cur[i]=head[i];
queue<int>q; q.push(S);
dep[S]=1;
while (!q.empty()){
int x=q.front(); q.pop();
for(int i=head[x];i!=-1;i=e[i].next){
int y=e[i].to;
if(dep[y]||!e[i].val) continue;
dep[y]=dep[x]+1;
q.push(y);
}
}
return dep[T];
}
int dfs(int x,int T,int In){
if(x==T) return In;
int Out=0;
for(int i=cur[x];i!=-1;i=e[i].next){
int y=e[i].to; cur[x]=i;
if(dep[y]!=dep[x]+1||!e[i].val) continue;
int res=dfs(y,T,min(e[i].val,In-Out));
e[i].val-=res,e[i^1].val+=res;
Out+=res;
if(In==Out) return Out;
}
if(In!=Out) dep[x]=0;
return Out;
}
int Dinic(){
int ans=0;
while (bfs(s,t)) ans+=dfs(s,t,INF);
return ans;
}
};
int main()
{
int t=read();
while (t--)
{
int n=read(),m=read();
Max_Flow flow; flow.s=0,flow.t=2*n+5;
for(int i=1;i<=n;i++)
flow.add_e(flow.s,i,1),
flow.add_e(i+n,flow.t,1);
for(int i=1;i<=m;i++){
int u=read(),v=read();
flow.add_e(u,v+n,1);
}
int ans=flow.Dinic();
printf("%d\n",n-ans);
}
return 0;
}
最
小
可
相
交
路
径
覆
盖
：
每
一
条
路
径
经
过
的
顶
点
可
以
相
同
最小可相交路径覆盖：每一条路径经过的顶点可以相同
最
小
可
相
交
路
径
覆
盖
：
每
一
条
路
径
经
过
的
顶
点
可
以
相
同
c
o
d
e
:
code:
c
o
d
e
:
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <bitset>
#include <vector>
#include<cstring>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
typedef unsigned long long ull;
#define Ios() ios::sync_with_stdio(false);
inline int read(){int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
const int N = 3e6+5;
const int maxn = 1e3+10;
int head[maxn],tot;
struct E{
int to,next,val;
}e[N];
class Max_Flow
{
public:
int s,t;
int tot,head[maxn],dep[maxn],cur[maxn];
Max_Flow(){tot=0;memset(head,-1,sizeof(head));}
void clear(){tot=0;memset(head,-1,sizeof(head));}
void add_e(int u,int v,int w){
e[tot].to=v,e[tot].next=head[u],e[tot].val=w;
head[u]=tot++;
e[tot].to=u,e[tot].next=head[v],e[tot].val=0;
head[v]=tot++;
}
bool bfs(int S,int T){
for(int i=0;i<maxn;i++) dep[i]=0,cur[i]=head[i];
queue<int>q; q.push(S);
dep[S]=1;
while (!q.empty()){
int x=q.front(); q.pop();
for(int i=head[x];i!=-1;i=e[i].next){
int y=e[i].to;
if(dep[y]||!e[i].val) continue;
dep[y]=dep[x]+1;
q.push(y);
}
}
return dep[T];
}
int dfs(int x,int T,int In){
if(x==T) return In;
int Out=0;
for(int i=cur[x];i!=-1;i=e[i].next){
int y=e[i].to; cur[x]=i;
if(dep[y]!=dep[x]+1||!e[i].val) continue;
int res=dfs(y,T,min(e[i].val,In-Out));
e[i].val-=res,e[i^1].val+=res;
Out+=res;
if(In==Out) return Out;
}
if(In!=Out) dep[x]=0;
return Out;
}
int Dinic(){
int ans=0;
while (bfs(s,t)) ans+=dfs(s,t,INF);
return ans;
}
};
int n,m;
int dis[505][505];
void floyd()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
if(n==0&&m==0) break;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) dis[i][j]=INF;
for(int i=1;i<=m;i++){
int u=read(),v=read();
dis[u][v]=0;
}
floyd();
Max_Flow flow; flow.s=0,flow.t=2*n+5;
for(int i=1;i<=n;i++)
flow.add_e(flow.s,i,1),
flow.add_e(i+n,flow.t,1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!dis[i][j]) flow.add_e(i,j+n,1);
int ans=flow.Dinic();
printf("%d\n",n-ans);
}
return 0;
}