太极剑
题目描述
在学习太极之后,Bob 要求 Alice 教他太极剑。Alice 告诉他首先需要通过一项基本剑术测试。测试要求 Bob 尽可能快地切断 $n$ 根绳子。
所有绳子的端点两两不同,所以共有 $2n$ 个端点。这些端点被捆在一个圆上,等距离分布。我们把这些端点按顺时针方向编号为 $1$ 到 $2n$。
Bob 每次切割的轨迹是一条直线,可以将所有与这条直线相交的绳子切断,他想知道至少多少次可以切断所有的绳子。
输入输出格式
输入格式
第一行一个整数 $n(1 \leq n \leq 2 \times 10^5)$,表示绳子的个数。
接下来 $n$ 行,每行两个整数 $a_i, b_i(1 \leq a_i, b_i \leq 2n, a_i \not= b_i)$,表示第 $i$ 根绳子的两个端点的编号。
输出格式
一行一个整数,表示答案。
输入输出样例
输入样例 #1
2
1 2
3 4
输出样例 #1
1
输入样例 #2
3
1 2
3 4
5 6
输出样例 #2
2
输入样例 #3
3
1 3
2 4
5 6
输出样例 #3
1
说明
样例一解释:![](https://cdn.luogu.com.cn/upload/pic/19179.png)
样例二解释:![](https://cdn.luogu.com.cn/upload/pic/19180.png)
样例三解释:![](https://cdn.luogu.com.cn/upload/pic/19181.png)