最小路径覆盖数:
对于一个DAG（有向无环图），选取最少条路径，使得每个 顶点属于且仅属于一条路径。路径长度可以为零；（有向图中找一些路径，使之覆盖了图中的所有顶点，就是任意一个顶点都跟那些路径中的某一条关联，且任何一个顶点有且只有一个与之关联）

最小路径覆盖数（最少边覆盖）=顶点数-最大匹配数；

思路：把每个点都拆成两个点，分为入点和出点，如果 u 到 v 有边，那么我们就让 u 的入点连向 v 的出点 ， 匈牙利 算出最大匹配。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxx=1005;
const int inf=0x3f3f3f3f;
int used[maxx];
int line[maxx][maxx];
int vis[maxx];
int n,m;
int nxt[maxx];
void init(){memset(used,0,sizeof(used));memset(vis,0,sizeof(vis));memset(line,0,sizeof(line));memset(nxt,-1,sizeof(nxt));
}
int Find(int x){for(int i=1;i<=n;i++){if(used[i]==0&&line[x][i]==1){used[i]=1;if(nxt[i]==-1||Find(nxt[i])){nxt[i]=x;return true;}}}return false;
}
int match(){int sum=0;for(int i=1;i<=n;i++){memset(used,0,sizeof(used));if(Find(i)){sum++;}}return sum;
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%d %d",&n,&m);init();for(int i=1;i<=m;i++){int a,b;scanf("%d %d",&a,&b);line[a][b]=1;}int ans=match();cout<<n-ans<<endl;} return 0;
}