CF1411C Peaceful Rooks

给定一个 $n \times n$ 的国际象棋棋盘。棋盘的行和列编号从 $1$ 到 $n$。单元格 $(x, y)$ 位于第 $x$ 列和第 $y$ 行的交点。 “车”是一种国际象棋棋子，每一步可以沿着垂直或水平方向移动任意格数。棋盘上有 $m$ 个车（$m < n$），它们被放置在棋盘上，且任意两个车不会互相攻击。也就是说，没有任意一对车处于同一行或同一列。 每一步，你可以选择一个车，将其沿垂直或水平方向移动任意格数。移动后，该车不能被其他任何车攻击。请问，最少需要多少步才能将所有车都放到主对角线上？ 棋盘的主对角线是所有 $(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$。

对于每个测试用例，输出一个整数，表示将所有车放到主对角线上所需的最小步数。 可以证明一定存在可行方案。

前三个测试用例的可能移动方案： 1. $(2, 3) \to (2, 2)$ 2. $(2, 1) \to (2, 3)$，$(1, 2) \to (1, 1)$，$(2, 3) \to (2, 2)$ 3. $(2, 3) \to (2, 4)$，$(2, 4) \to (4, 4)$，$(3, 1) \to (3, 3)$，$(1, 2) \to (1, 1)$ 由 ChatGPT 4.1 翻译