本题没有可用的提交语言。

题目描述

给定$n$个整数寄存器$r_1, r_2, \ldots, r_n$，我们定义一个比较交换指令$\text{CE}(a, b)$，其中$a, b$是寄存器索引（$1 \leq a < b \leq n$）：

$\text{CE}(a, b)$:
如果寄存器$r_a$的内容大于$r_b$的内容，则交换$r_a$和$r_b$的值。

一个比较交换程序（简称$\text{CE}$程序）是任意有限的比较交换指令序列。如果一个$\text{CE}$程序在执行后，寄存器$r_1$始终包含所有寄存器中的最小值，则称该程序为最小值查找程序。如果该程序在删除任意一条$\text{CE}$指令后仍是最小值查找程序，则称其为可靠的。

给定一个$\text{CE}$程序$P$，问最少需要在程序$P$的末尾添加多少条指令，才能使其成为一个可靠的最小值查找程序？

示例
考虑以下针对3个寄存器的$\text{CE}$程序：
$\text{CE}(1, 2); \text{CE}(2, 3); \text{CE}(1, 2)$。
为了使该程序成为可靠的最小值查找程序，只需添加两条指令：$\text{CE}(1, 3)$和$\text{CE}(1, 2)$。

任务
编写一个程序，对每个数据集：
读取$\text{CE}$程序的描述；
计算最少需要添加的$\text{CE}$指令数量；
输出结果。

输入格式

第一行输入一个正整数$d$，表示数据集的数量（$1 \leq d \leq 10$）。接下来是$d$个数据集。

每个数据集由两行组成：
第一行包含两个整数$n$和$m$，用空格分隔（$2 \leq n \leq 10\,000$，$0 \leq m \leq 25\,000$）。$n$是寄存器的数量，$m$是程序的指令数量。
第二行包含$2m$个整数，用空格分隔，表示程序本身。第$2j-1$和第$2j$位的整数$a_j$和$b_j$（$1 \leq a_j < b_j \leq n$）是程序中第$j$条指令的参数。

输出格式

输出$d$行，每行一个整数，表示对应该数据集需要添加的最少指令数量。

输入样例 1

1  
3 3  
1 2 2 3 1 2  

输出样例 1

2  

来源

中欧 2001