题目描述

银河系中有 $n$ 个行星，许多无向曲速通道连接着它们。$6000$ 年前，Spinel 对这些行星进行了一次深度优先搜索，访问了所有的行星，并按照被发现的顺序将它们从 $1$ 到 $n$ 进行了标号。

自那以后，许多通道已经损坏，现在只剩下 $m$ 条通道可以使用。Spinel 想知道，需要修建多少条新的通道，才能保证能够进行一次深度优先搜索，并且访问顺序正好与 $6000$ 年前标号时完全一致。

回顾一下深度优先搜索 (DFS) 算法。它输入一个图 $G$ 和 $G$ 的一个顶点 $v$，并将所有从 $v$ 可达的顶点标记为已访问。

下面是递归实现 DFS 的伪代码：

procedure DFS(G, v) is
    label v as discovered
    for all vertices w that there exists an edge between v and w do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

输入格式

有多组测试数据。第一行包含一个整数 $T$，表示测试数据组数。对于每一组数据：

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^5$），分别表示行星的数量和剩余通道的数量。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示存在一条连接 $u_i$ 和 $v_i$ 的通道。

保证所有测试数据中 $(n + m)$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行一个整数，表示至少需要修建多少条新的曲速通道。

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

0
2
1

提示

对于第二组样例，可以在行星 $1$ 和 $2$ 之间添加一条通道，在行星 $2$ 和 $3$ 之间再添加一条通道。

对于第三组样例，可以在行星 $2$ 和 $3$ 之间添加一条通道。

由 ChatGPT 5 翻译