Doremy's Drying Plan (Easy Version)
Contest: Codeforces Round 906 (Div. 1)
Difficulty rating: 2000
Tags: brute force, data structures, dp, greedy, sortings

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 format:
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 format:
For each test case, output one integer — the maximum number of dry cities.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 2
1 5
6 10
2 2
3 7
5 8
1 4
100 6 2
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 2
9 20
3 3
10 11
11 13
6 18

Example output:
1
2
3
0
1000
15

Editorial:
We consider a brute force solution first.
At the beginning, we calculate number of intervals that cover position $$$i$$$ for each $$$i=1,2,\ldots,n$$$ by prefix sum. Now we can know the number uncovered positions. Let it be $$$A$$$. Then we need to calculate the number of new uncovered position after removing two intervals. Let it be $$$B$$$. So the answer in the end is $$$A + \max B$$$.
For calculating $$$B$$$, let's enumerate two intervals $$$I_1,I_2$$$.
• If they have no intersection, $$$B$$$ is equal to the number of positions that are covered exactly once in interval $$$I_1$$$ and $$$I_2$$$;
• If they have intersection. Let the intersection be $$$J$$$ (It is an interval). $$$B$$$ is equal to the number of positions that are covered exactly once in interval $$$I_1$$$ and $$$I_2$$$ plus the number of positions that are covered exactly twice in interval $$$J$$$;
The algorithm can be done in $$$O(n+m^2)$$$ time by prefix sum. For optimization, we should notice that:
In the "no intersection" case, we can just simply pick two best intervals.
In the "intersection" case, there are at most $$$n$$$ useful interval pairs. The proof and algorithm goes: for each position $$$i$$$, if it is covered by exactly $$$2$$$ intervals, then this interval pair is useful and may update the answer.
Great, but for code implementation, how do we find those interval pairs? For each interval $$$[l,r]$$$, we consider it as two events (like difference and prefix sum): it appears at position $$$l$$$, and disappears at position $$$r+1$$$. That way, set or just array is able to handle.
Time complexity $$$O(n+m)$$$.