CF2261D2 Come Be My Friend, Don't Be So Scared (Hard Version)

注意 D1 和 D2 的分数分布不同寻常。本题比 D1 显著更难。 这是本题的困难版本。这个版本与另一版本的区别在于， $0 \le m \le 2 \cdot 10^5$。只有你解决了所有版本的本题才能进行 Hack。 你正在躲避强大的 Lord Verity。 共有 $n$ 个可能的藏身点，沿着一行从左到右依次编号为 $1$ 到 $n$。你只能藏在其中一个点。 为了找到你的位置，Lord Verity 可以安装特殊的探测器。每个探测器可以覆盖一段连续的藏身点，并报告你是否藏在该区间内。所有探测器会同时被激活，因此所有探测器的区间在得到任何探测结果之前就要确定。 Lord Verity 已经有 $m$ 个探测器，第 $i$ 个探测器覆盖从 $l_i$ 到 $r_i$ 的藏身点。请你计算 Lord Verity 至少还需要安装多少个额外的探测器，才能保证无论你藏在哪个位置，所有探测器的报告都足以唯一确定你的位置。你还需要输出一种安装方案。

每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来描述每个测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 2\cdot 10^5$），表示藏身点的数量以及 Lord Verity 已经拥有的探测器数量。 接下来 $m$ 行，每行两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 个探测器覆盖从 $l_i$ 到 $r_i$ 的藏身点。 保证没有两个给定的探测器覆盖相同的区间。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，所有测试用例中 $m$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，首先输出一个整数 $k$，表示还需额外安装的探测器的最小数量。 随后输出 $k$ 行，每行两个整数 $u_j$ 和 $v_j$（$1 \le u_j \le v_j \le n$），表示第 $j$ 个新增探测器覆盖的区间是从 $u_j$ 到 $v_j$。 如果有多种方案，输出任意一种均可。

在第一个测试用例中，只有一个藏身点，因此 Lord Verity 必然知道你在那里，不需要探测器。 在第二个测试用例中，有两个藏身点。Lord Verity 只需安装一个覆盖 $u = v = 1$ 的探测器，就能判断你是在位置 $1$ 还是 $2$，据探测结果即可唯一确定你的位置。 在第五个测试用例中，可以证明仅凭现有的探测器，Lord Verity 就能唯一确定你的藏身点。 由 ChatGPT 5 翻译