Background

This problem is a harder version of P16280. The only difference between the two versions is that in this problem, $n \le 5 \times 10^4$.

Problem Description

Given $n$ closed intervals $[l_1,r_1],[l_2,r_2],\dots,[l_n,r_n]$. Find the maximum number of intervals that can be selected such that for any two selected intervals that intersect$^{\bm{\dagger}}$, they share a common endpoint$^{\bm{\ddagger}}$.

$\bm\dagger$ Two closed intervals $[l_1,r_1]$ and $[l_2,r_2]$ are said to intersect if and only if $l_2 \le r_1$ and $l_1 \le r_2$.
$\bm\ddagger$ Two closed intervals $[l_1,r_1]$ and $[l_2,r_2]$ are said to share a common endpoint if and only if $l_1=l_2$, $l_1=r_2$, $r_1=l_2$, or $r_1=r_2$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

Then follow $T$ test cases. For each test case:

• The first line contains a positive integer $n$.
• The next $n$ lines each contain two positive integers $l_i,r_i$.

Output Format

For each test case, output one line containing one integer, representing the maximum number of intervals that can be selected.

4
3
1 3
2 2
1 1
5
1 3
2 3
4 5
3 5
1 4
8
1 4
2 4
3 4
1 2
2 3
1 3
3 5
4 5
16
1 4
2 4
3 4
1 2
2 3
1 3
3 5
4 5
5 8
6 8
7 8
5 6
6 7
5 7
7 9
8 9

2
4
6
12

Hint

"Sample #1 Explanation"

For the first test case, you can select two intervals, $[1,1]$ and $[1,3]$. It can be proven that there is no way to select more intervals.

For the second test case, you can select four intervals, $[1,3]$, $[2,3]$, $[4,5]$, and $[3,5]$. It can be proven that there is no way to select more intervals.

Constraints

This problem has no subtasks.

For all testdata, it is guaranteed that $1 \le T \le 5$, $1 \le n \le 5 \times 10^4$, $1 \le l_i \le r_i \le 2n$.

Translated by ChatGPT 5