P16280 「MierOI R1」Eternal

If you have already completed this problem, you can consider the [advanced version of this problem](https://www.luogu.com.cn/problem/P16348).

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 all **intersecting$^{\bm{\dagger}}$** intervals among the selected ones **share a common endpoint$^{\bm{\ddagger}}$**. --- $\bm\dagger$ Two closed intervals $[l_1,r_1],[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],[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 contains multiple test cases.** The first line of the input contains a positive integer $T$, indicating the number of test cases. Then, the $T$ test cases follow sequentially. 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 a single line containing a non-negative integer, representing the maximum number of intervals that can be selected.

#### Explanation for Sample #1 For the first test case, we can select 2 intervals: $[1,1]$ and $[1,3]$. It can be proven that there is no way to select more intervals. For the second test case, we can select 4 intervals: $[1,3], [2,3], [4,5]$, and $[3,5]$. It can be proven that there is no way to select more intervals. #### Data Range **This problem uses bundled subtasks.** For all test cases, it is guaranteed that $1 \le T \le 5$, $1 \le n \le 1\,000$, and $1 \le l_i \le r_i \le 2n$. ::cute-table{tuack} | Subtask | $n \le$ | Special Property | Score | |:-:|:-:|:-:|:-:| | $1$ | $10$ | None | $15$ | | $2$ | $200$ | ^ | $25$ | | $3$ | $1\,000$ | A | $10$ | | $4$ | ^ | B | $10$ | | $5$ | ^ | None | $40$ | - Special Property A: Any two given intervals do not share a common endpoint. - Special Property B: Any two given intervals intersect.