P14121 [SCCPC 2021] Don't Really Like How The Story Ends

银河系中有 $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$。

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

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