#P18390. Chords
Chords
Chords
圆周上有2n个等间距的点,按顺时针方向编号1到2n。把这些点两两配对,得到n条弦,每个点恰好属于一条弦。
求最多能选择多少条弦,使所选弦两两不相交,只需输出这个最大数量。
输入格式
第一行一个整数n,1≤n≤100000。
接下来n行,每行两个整数a_i、b_i,表示一条弦连接的两个点,满足1≤a_i<b_i≤2n。所有2n个端点编号两两不同。
**原题的数据生成约定:**除样例外,各测试先选定n和随机种子,随机生成1到2n的一个排列,再依次把相邻的两个数分为一对;每对内可交换顺序以满足a_i<b_i。样例为人工制作,也必须正确求解。此随机输入约定是原题的一部分。
输出格式
输出一个整数,表示两两不相交弦集的最大大小。
样例
样例输入 1
5
1 2
4 10
7 9
3 5
6 8
样例输出 1
3
说明
可以选择连接(1,2)、(3,5)、(6,8)的三条弦。