P16348 "MierOI R1" Eternal (Hard ver.)

This problem is a harder version of [P16280](https://www.luogu.com.cn/problem/P16280). The only difference between the two versions is that in this problem, $n \le 5 \times 10^4$.

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$.

**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$.

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

#### "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