SP109 EXCHNG - Exchanges

设有 $n$ 个整数寄存器 $r_1, r_2, \ldots, r_n$，我们定义一个 "比较-交换" 指令 $\text{CE}(a, b)$，其中 $a, b$ 是寄存器的索引，需要满足条件 $1 \le a < b \le n$。指令的具体操作如下： ``` CE(a, b):: 如果寄存器 ra 的内容大于寄存器 rb 的内容，则交换 ra 和 rb 的内容； ``` 一个由若干比较-交换指令组成的序列称为比较-交换程序（简称 CE 程序）。如果一个 CE 程序不论在何种情况下执行完后，寄存器 $r_1$ 总是含有所有寄存器中的最小值，则称该程序为 "最小值查找程序"。如果在删除任意一条比较-交换指令后，该程序仍然是最小值查找程序，则称这个程序是 "可靠的"。 现给定一个 CE 程序 $P$，需要确定至少需要在 $P$ 的末尾添加多少条指令，才能使其成为一个可靠的最小值查找程序。 例如，对于 3 个寄存器的 CE 程序：$\text{CE}(1, 2), \text{CE}(2, 3), \text{CE}(1, 2)$，只需在末尾添加两条指令：$\text{CE}(1, 3)$ 和 $\text{CE}(1, 2)$，即可使其变得可靠。 ### 任务 编写一个程序，需完成以下功能： - 读取一个 CE 程序的详细描述， - 计算为使其成为可靠的最小值查找程序需要在末尾添加的最少指令数， - 输出结果。

输入的第一行包含一个正整数 $d$，表示一共有多少组数据，$1 \le d \le 10$。 接下来的每组数据包含两行： - 第一行有两个整数 $n$ 和 $m$，用空格分隔，$2 \le n \le 10000$，$0 \le m \le 25000$。其中，$n$ 表示寄存器的数量，$m$ 表示现有程序的指令数。 - 第二行有 $2m$ 个整数，用空格分隔，表示程序序列。对于每个 $j$，整数 $a_j$ 和 $b_j$ 位于位置 $2j-1$ 和 $2j$ 上，且须满足 $1 \le j \le m$，$1 \le a_j < b_j \le n$，分别为程序中的第 $j$ 条指令的参数。

共输出 $d$ 行，每行为一组数据的结果。第 $i$ 行（$1 \le i \le d$）输出需要在第 $i$ 个输入程序的末尾添加的最少指令数，以使其成为一个可靠的最小值查找程序。 **本翻译由 AI 自动生成**