← 返回题目列表

AtCoder · abc410_g

G. 最长的弦链

中文机器翻译题面 查看原题

分数: 575 点

问题陈述

有 2N 成对不同点,编号为 1 to 2N,在一个圆圈上。从点出发 1 顺时针方向,点排列为点 2,点 3, ..., 点 2N.

你被给予 N 这个圆上的和弦。的端点 i第和弦是点 A_i 和 B_i,以及 2N 值 A_1,\ldots,A_N,B_1,\ldots,B_N 都是不同的。

在此圆上依次执行以下操作各一次:

  1. 其中 N 和弦,选择任意数量的和弦,使两个选定的和弦不相交,然后删除剩余的和弦。
  2. 向圆中自由添加一个和弦。

求运算完成后弦之间最大可能的交点数。

约束

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i,B_i \leq 2N
  • 的 2N 值 A_1, \ldots, A_N,B_1,\ldots,B_N 成对不同。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

输出答案。


示例输入 1

3
1 5
6 3
4 2

示例输出 1

2

最初,有 3 和弦放在圆上,如图所示。
删除和弦连接点后 3 和 6 并通过运算添加新的和弦,则和弦之间的交点个数为 2.

Figure

不可能使弦之间的交点数量 3 或更多,所以答案是 2.

最后添加的弦的端点不需要是任何点 1,\ldots, 2N.


示例输入 2

4
1 8
2 7
3 6
4 5

示例输出 2

4

示例输入 3

3
1 2
3 4
5 6

示例输出 3

2