{"problem":{"name":"[ICPC 2022 Jinan R] Set of Intervals","description":{"content":"Prof. Pang has a multi-set of intervals $S=\\{[l_i,r_i]\\}$($l_i<r_i$). Prof. Pang will perform the following operation for $|S|-1$ times: - Select two intervals $[a,b]$ and $[c,d]$ from $S$, and then","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9674"},"statements":[{"statement_type":"Markdown","content":"Prof. Pang has a multi-set of intervals $S=\\{[l_i,r_i]\\}$($l_i<r_i$).\n\nProf. Pang will perform the following operation for $|S|-1$ times:\n\n- Select two intervals $[a,b]$ and $[c,d]$ from $S$, and then choose two integers $x,y$ satisfying $x\\in [a,b], y\\in [c,d], x<y$. After that, delete $[a,b]$ and $[c,d]$ from $S$, and add $[x,y]$ to $S$.\n\nIt's easy to find that $S$ contains exactly one interval after the operations, and Prof. Pang will get the interval as a gift.\n\nNow Prof. Pang wants you to calculate how many different intervals he can get.\n\n## Input\n\nThe first line contains one integer $T~$($1\\le T \\le 10^4$), the number of test cases.\n\nFor each test case, the first line contains one integer $n~$($1\\le n\\le 10^5$) --- the size of $S$. Each of the following $n$ lines contains two integers $l_i$ and $r_i~$($1\\le l_i<r_i\\le 10^9$), describing the $i$-th interval in $S$.\n\nIt is guaranteed that the sum of $n$ over all test cases is no more than $10^5$.\n\n## Output\n\nFor each test case, output one line containing the answer to Prof. Pang's question.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9674","tags":["2022","O2优化","ICPC","Ad-hoc","分类讨论","济南"],"sample_group":[["4\n1\n1 1000000000\n2\n1 1000000000\n1 1000000000\n4\n1 2\n3 4\n5 6\n7 8\n4\n1 3\n2 4\n5 8\n6 7","1\n499999999500000000\n26\n28"]],"created_at":"2026-03-03 11:09:25"}}