题目描述

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

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

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

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

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

输入格式

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

每组测试数据第一行包含整数 $N$（交叉口数量），第二行包含整数 $M$（道路数量）。

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

输出格式

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

每个结果占一行。

样例

输入样例：

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

输出样例：

2
1

样例解释

第一组数据：$N=4, M=3$，道路：3→4, 1→3, 2→3。

图结构：

1 → 3 → 4
2 ↗

这是一个 DAG。最少需要 2 名士兵：

• 一名从 1 出发：1→3→4
• 另一名从 2 出发：2→3（但 3 已被走过，所以不行，因此需要两名独立路径） 实际上，可以安排士兵分别从 1 和 2 出发，1走 1-3-4，2走 2，但这样需要 2 名。

另一种方式：一名士兵从 2 出发走到 3，然后 3 不能去 4，因为 3 已经被走过？ 题目要求每个交叉口只能被一个士兵走一次，所以 3 被走过之后不能再走。
因此 2→3 和 1→3 冲突，需要两名士兵。

第二组数据：$N=3, M=3$，道路：1→3, 1→2, 2→3。

图结构：

1 → 2 → 3
 ↘_____↗
  直接1→3

最少需要 1 名士兵，从 1 出发可以走 1→2→3 或 1→3，总之能覆盖所有点。

数据范围

• $0 < N \leq 120$
• $1 \leq X, Y \leq N$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB