← 返回题目列表

Codeforces · 100/J

J. 间隔着色

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

Aryo 的 2418 岁生日有很多间隔。他真的很兴奋,决定用一些颜色来为所有这些间隔着色。他为自己制定了一个简单的规则。如果不存在同时满足以下条件的三个区间 a、b 和 c,他称着色为“好”:

- a、 b 和 c 的颜色相同,
- $$a \cap b \neq \varnothing$$,
- $$b \cap c \neq \varnothing$$,
- $$a \cap c = \varnothing$$。

此外,他发现对于每个区间 i 和 j,i 中至少有一个点不在 j 中。

给定一组间隔。你必须找到最小的数字 k,这样 Aryo 才能找到 k 种颜色的漂亮颜色。

输入

第一行包含一个整数 n (1 ≤ n ≤ 103),即间隔数。

以下 n 行每行包含一个区间描述。每个区间由两个数字 si、ei 描述,它们是该区间的起点和终点(- 105 < si,ei < 105,si ≤ ei)。为清楚起见,请参阅示例。方括号代表包含对应的端点,圆括号代表排除对应的端点。

输出

写一个整数 k — 良好着色所需的最小颜色数。

示例

输入 #1

2
[1,2)
(3,4]

输出 #1

1

输入 #2

3
[1,3]
[2,6]
(5,7)

输出 #2

2