← 返回题目列表

Codeforces · 1411/C

C. 和平的乌鸦

中文机器翻译题面 查看原题

给你一个 $$$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)$$$