题目描述

考虑一个城镇，所有街道都是单行道，每条街道都从一个十字路口通向另一个。而且已知，从一个十字路口出发，沿着城镇的街道行走，永远不可能回到同一个十字路口，即城镇的街道不构成循环。

在这些假设条件下，你的任务是编写一个程序，找出可以降落在城镇并访问所有十字路口的最少伞兵数量，使得没有一个十字路口被多于一个伞兵访问。每个伞兵降落在一个十字路口，并可以沿着城镇的街道访问其他十字路口。每个伞兵的起始十字路口没有限制。

输入格式

你的程序应该读取一组组数据。输入文件的第一行包含数据组的数量。每组数据指定了城镇的结构，格式如下：

第一行包含一个正整数十字路口数量 $N$，即城镇中十字路口的数量。

第二行包含一个正整数街道数量 $M$，即城镇中的街道数量。

接下来的街道数量行，每行代表城镇中的一条街道，随机排序，表示城镇的街道。与第 $k$ 条街道对应的行（ $k \le M$ ）由两个正整数组成，用一个空格分隔：$S_k$（ $1 \le S_k \le N$ ）表示街道起点的十字路口编号，$E_k$（ $1 \le E_k \le N$）表示街道终点的十字路口编号。

相邻数据组之间没有空行。输入数据是正确的。

输出格式

对于每组输入数据，输出一个整数，即访问城镇所有十字路口所需的最少伞兵数量。

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

2
1

样例分析

样例中，第一组数据一个伞兵覆盖的路径为 $1 \to 3 \to 4$，一个伞兵的覆盖路径为 $2 \to 3$；第二组样例中一个伞兵就可以覆盖路径 $1 \to 2 \to 3$，也可以覆盖路径 $1 \to 3$。

数据范围与提示

对于$100 \%$ 的数据：$1 \le N \le 120$ ，$1 \le M \le 1000$。