给你一个 $$$n \times n$$$ 棋盘。棋盘的行和列从 $$$1$$$ 到 $$$n$$$ 进行编号。单元格 $$$(x, y)$$$ 位于列号 $$$x$$$ 和行号 $$$y$$$ 的交集处。
车是一个棋子,可以在一轮中垂直或水平移动任意数量的单元格。棋盘上放置了 $$$m$$$ 个车 ($$$m < n$$$),确保没有一对车会互相攻击。 IE。没有一对车共享一行或一列。
一回合内,您可以将其中一辆车垂直或水平移动任意数量的单元格。此外,它在移动后不应受到任何其他车的攻击。将所有车放在主对角线上所需的最少移动次数是多少?
棋盘的主对角线是所有单元格 $$$(i, i)$$$,其中 $$$1 \le i \le n$$$。
输入
第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^3$$$)。 $$$t$$$ 测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ - 棋盘的大小和车的数量($$$2 \leq n \leq 10^5$$$, $$$1 \leq m < n$$$)。接下来的 $$$m$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ - 车的位置,第 $$$i$$$ 车被放置在单元格 $$$(x_i, y_i)$$$ ($$$1 \leq x_i, y_i \leq n$$$) 中。保证在初始放置中不会有两个车互相攻击。
所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个 $$$t$$$ 测试用例,都会打印一个整数 - 将所有车放在主对角线上所需的最小移动次数。
可以证明这总是可能的。
示例
输入 #1
4 3 1 2 3 3 2 2 1 1 2 5 3 2 3 3 1 1 2 5 4 4 5 5 1 2 2 3 3
输出 #1
1 3 4 2
注意
前三个测试用例的可能移动:
1. $$$(2, 3) \ 到 (2, 2)$$$
2. $$$(2, 1) \ 到 (2, 3)$$$, $$$(1, 2) \ 到 (1, 1)$$$, $$$(2, 3) \ 到 (2, 2)$$$
3. $$$(2, 3) \ 到 (2, 4)$$$, $$$(2, 4) \ 到 (4, 4)$$$, $$$(3, 1) \ 到 (3, 3)$$$, $$$(1, 2) \到 (1, 1)$$$