CF1889C1 Doremy's Drying Plan (Easy Version)

本题的两个版本仅在 $k$ 的限制、时间限制和内存限制上有所不同。只有在所有版本都被解决的情况下，你才能进行 hack。 Doremy 生活在一个多雨的国家，这个国家有 $n$ 个城市，编号从 $1$ 到 $n$。 天气预报预测了接下来 $m$ 天的降雨分布。在第 $i$ 天，将会在区间 $[l_i, r_i]$ 的城市下雨。如果在接下来的 $m$ 天里某个城市从未下过雨，则称该城市为干燥城市。 Doremy 拥有一种特殊能力。她可以选择 $k$ 天（在简单版本中，$k=2$），在这几天内不会下雨。Doremy 想要计算在使用这种特殊能力后，最多能有多少个干燥城市。

输入包含多组测试数据。第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。 每组测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1\le n\le 2\cdot 10^5$，$2 \le m \le 2\cdot 10^5$，$k=2$），分别表示城市数量、天数和 Doremy 能阻止下雨的天数。 接下来有 $m$ 行，每行包含两个整数 $l_i$、$r_i$（$1\le l_i\le r_i\le n$），表示第 $i$ 天下雨覆盖的城市区间。 保证所有测试用例中 $n$ 的总和与 $m$ 的总和不超过 $2\cdot 10^5$。

对于每组测试用例，输出一个整数，表示最多能有多少个干燥城市。

在第一个测试用例中，如果 Doremy 阻止 - 第 $1,2$ 天的降雨，则城市 $2$ 会保持干燥； - 第 $2,3$ 天的降雨，则没有城市会保持干燥； - 第 $1,3$ 天的降雨，则没有城市会保持干燥； 因此最多只有 $1$ 个干燥城市。 在第二个测试用例中，如果 Doremy 阻止 - 第 $1,2$ 天的降雨，则城市 $1,2$ 会保持干燥； - 第 $2,3$ 天的降雨，则城市 $4,5$ 会保持干燥； - 第 $1,3$ 天的降雨，则城市 $1,5$ 会保持干燥。 因此最多有 $2$ 个干燥城市。 在第三个测试用例中，最优的做法是阻止第 $2,5$ 天的降雨。 在第四个测试用例中，总有 $4$ 天的降雨覆盖了所有城市，无法避免。 由 ChatGPT 4.1 翻译