E1. Doremy's Drying Plan (Easy Version)

The only differences between the two versions of this problem are the constraint on $k$, the time limit and the memory limit. You can make hacks only if all versions of the problem are solved.

Doremy lives in a rainy country consisting of $n$ cities numbered from $1$ to $n$.

The weather broadcast predicted the distribution of rain in the next $m$ days. In the $i$-th day, it will rain in the cities in the interval $[l_i, r_i]$. A city is called dry if it will never rain in that city in the next $m$ days.

It turns out that Doremy has a special power. She can choose $k$ days (in the easy version, $k = 2$), and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.

Input

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains three integers $n$, $m$ and $k$ ($1\le n\le 2\cdot 10^5$, $2 \le m \le 2\cdot 10^5$, $k = 2$) — the number of cities, the number of days, and the number of days of rain that Doremy can prevent.

Then, $m$ lines follow. The $i$-th line contains two integers $l_i$, $r_i$ ($1\le l_i\le r_i\le n$) — the rain coverage on day $i$.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2\cdot 10^5$.

Output

For each test case, output one integer — the maximum number of dry cities.

Example

input

output

Note

In the first test case, if Doremy prevents

rain $1,2$, then city $2$ will be dry;
rain $2,3$, then no city will be dry;
rain $1,3$, then no city will be dry;

So there is at most $1$ dry city.

In the second test case, if Doremy prevents

rain $1,2$, then city $1,2$ will be dry;
rain $2,3$, then city $4,5$ will be dry;
rain $1,3$, then city $1,5$ will be dry.

So there are at most $2$ dry cities.

In the third test case, it is optimal to prevent rain $2,5$.

In the forth test case, there is always $4$ days of rain that wets all the cities and cannot be prevented.

解题思路

这道题思路很好想，但实现起来很难。

由于最多只能删除两个区间，因此如果某个下标至少被 $3$ 个区间覆盖那么一定不能将其减少为 $0$ 次。假设 $s_i$ 表示下标 $i$ 被覆盖的次数，因此只用考虑 $s_i = 0$，$s_i = 1$，$s_i = 2$ 的下标。

其中对于只被覆盖 $1$ 次的下标，那么只需找到含 $s_i = 1$ 的下标数量最多的两个区间，两个数量加起来就是删除两个区间使只被覆盖 $1$ 次的下标变为 $0$ 的最大数量。如果这两个区间相交呢？并不影响结果，因为相交那部分必然有 $s_i \geq 2$，而由于现在只考虑将 $s_i = 1$ 的下标变为 $0$，故不用加上 $s_i = 2$ 的下标数量（下面的情况会考虑到）。实现的话只需枚举所有区间，维护最大值和次大值即可。

再考虑被覆盖 $2$ 次的下标，只需考虑所有 $s_i = 2$ 的下标 $i$，找到覆盖 $i$ 的两个区间即可。假设为 $[l_1, r_1]$ 和 $[l_2, r_2]$，那么删除这两个区间可能会让 $s_i = 1$ 和 $s_i = 2$ 的下标变 $0$。这两个区间的交集是 $[\max\{ l_1, l_2 \}, \min\{ r_1, r_2 \}]$，那么就会让其中 $s_i = 2$ 的下标变 $0$。这两个区间的并集是 $[\min\{ l_1, l_2 \}, \max\{ r_1, r_2 \}]$，那么就会让其中 $s_i = 1$ 的下标变 $0$。

下面讲一下如何找到覆盖下标 $i$ 的两个区间。首先对区间按左端点从小到大排序，然后从小到大枚举所有下标 $i$，开一个 $\text{std::multiset}$ 来维护覆盖的区间，对于 $s_i = 2$ 的下标 $i$，把所有左端点不超过 $i$ 的区间压入集合中，再把集合中所有右端点小于 $i$ 的集合删掉，此时集合的大小一定为 $2$，这就找到覆盖 $i$ 的两个区间了。

因此只用考虑以上两种情况中，让下标变成 $0$ 的最多数量，最后还要加上 $s_0$。

AC 代码如下，时间复杂度为 $O(n \log{m})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10;

PII p[N];
int s[N], s1[N], s2[N];

void solve() {
    int n, m;
    scanf("%d %d %*d", &n, &m);
    memset(s, 0, n + 10 << 2);
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        s[l]++, s[r + 1]--;
        p[i] = {l, r};
    }
    sort(p + 1, p + m + 1);
    for (int i = 1; i <= n; i++) {
        s[i] += s[i - 1];    // 下标i被覆盖的次数
        s1[i] = s1[i - 1] + (s[i] == 1);    // 前缀中s[i]=1的下标数量
        s2[i] = s2[i - 1] + (s[i] == 2);    // 前缀中s[i]=2的下标数量
    }
    int m1 = 0, m2 = 0;    // 找到含s[i]=1的下标最多的两个区间
    for (int i = 1; i <= m; i++) {
        int t = s1[p[i].second] - s1[p[i].first - 1];
        if (t >= m1) m2 = m1, m1 = t;
        else if (t > m2) m2 = t;
    }
    int ret = m1 + m2;
    multiset<PII> st;
    for (int i = 1, j = 1; i <= n; i++) {
        if (s[i] == 2) {    // i被覆盖了两次
            while (j <= m && p[j].first <= i) {    // 把左端点不超过i的区间加进来
                st.insert({p[j].second, p[j].first});
                j++;
            }
            while (!st.empty() && st.begin()->first < i) {    // 删掉右端点小于i的区间
                st.erase(st.begin());
            }
            // 此时集合的大小一定恰好是2
            int l = max(st.begin()->second, st.rbegin()->second);
            int r = min(st.begin()->first, st.rbegin()->first);
            int t = s2[r] - s2[l - 1];    // 两个区间的交集中s[i]=2的下标数量
            l = min(st.begin()->second, st.rbegin()->second);
            r = max(st.begin()->first, st.rbegin()->first);
            t += s1[r] - s1[l - 1];    // 两个区间的并集中s[i]=1的下标数量
            ret = max(ret, t);
        }
    }
    printf("%d\n", ret + count(s + 1, s + n + 1, 0));    // 加上s[i]=0的下标数量
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    
    return 0;
}