题目描述

在一个银河系中有 $n$ 个星球，许多无向的“跃迁隧道”连接着它们。5000 年前，梦梦使用深度优先搜索（DFS）遍历了这些星球，访问了所有星球，并按照发现顺序将它们标记为 $1$ 到 $n$。

但自那以后，许多跃迁隧道已经损坏，现在只有 $m$ 条隧道仍在工作。梦梦希望知道，至少需要修建多少条新的隧道，才能使深度优先搜索的发现顺序完全与 5000 年前的标记顺序一致。

深度优先搜索（DFS）算法的伪代码如下：

procedure DFS(G, v) is

    label v as discovered

    for all vertices w such that there exists an edge between v and w do

        if vertex w is not labeled as discovered then

            recursively call DFS(G, w)

注意，在遍历 $v$ 的相邻星球 $w$ 时的顺序任意，只需要最终得到的 DFS 序是 $1\sim n$ 即可。

输入格式

第一行一个整数 $T$ 表示数据组数。对于每组数据：

第一行两个整数 $n,m$ 表示星球数和隧道数。

接下来 $m$ 行，每行两个整数 $u_i,v_i$ 表示一条仍在工作的，连接第 $u_i$ 个和第 $v_i$ 个星球的隧道。

输出格式

对于每组数据，输出一行一个整数表示最少需要修建的隧道数量。

输入样例

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

输出样例

0
2
1

说明提示

输入样例 #2

1
2 1
1 2

输出样例 #2

0

输入样例 #3

1
3 3
2 3
1 2
1 3

输出样例 #3

0

数据范围

对于 $30\%$ 的数据，$1\leq T\leq 10$，$1\leq n,m\leq 10$。

对于 $50\%$ 的数据，$1\leq T\leq 10$，$1\leq n,m\leq 10^3$。

对于另外 $10\%$ 的数据，保证给出的 $m$ 条隧道不成环。

对于 $100\%$ 的数据，$1\leq T\leq 10^4$，$1\leq n,m\leq 10^5$，$\sum (n+m)\leq 10^6$，$1\leq u_i,v_i\leq n$。