题目描述

一个城镇由 $N$ 个交叉口和 $M$ 个单向道路组成，每条道路从一个交叉口通向另一个交叉口。

从任何一个交叉口出发，经过城镇的街道都无法回到出发的交叉口，即城镇的街道无法形成一个循环。

现在要选择一些交叉口空降士兵，士兵可以沿着街道一直走到尽头。

要求空降士兵走遍所有的交叉口，并且每个交叉口只能被一个士兵走一次。

请问最少需要多少名士兵。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组测试数据第一行包含整数 $N$，第二行包含整数 $M$ (0<N≤120)。

接下来 $M$ 行，每行包含两个整数 $X$ 和 $Y$，表示存在一条道路从交叉口 $X$ 通向交叉口 $Y$ (1≤X,Y≤N)。

输出格式

每组数据输出一个整数，表示需要的最少士兵数目。

每个结果占一行。

输入输出样例

输入 #1

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

输出 #1

2
1

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=210;
vector<int>G[N];
int n,m,match[N],vis[N],tsp;
bool dfs(int x)
{
    for(int y:G[x])if(vis[y]!=tsp)
    {
        vis[y]=tsp;
        if(!match[y]||dfs(match[y]))
        {
            match[y]=x;
            return 1;
        }
    }
    return 0;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
		memset(G,0,sizeof(G));
        for(int i=1,x,y;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
        }       
        int cnt=0;
		memset(match,0,sizeof(match));
		memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            tsp=i;
            if(dfs(i)) cnt++;
        }
        printf("%d\n",n-cnt);
    }
    return 0;
}