布设鹰眼

G-14数据枢纽的安检门前，天花板上悬着十二个球形雷达——Echo说它们叫"鹰眼"，是Zero的眼睛。每个鹰眼有一个扇形扫描区，覆盖地面上一段扇形区域。任何移动的物体进入扫描区，都会触发警报。

"要通过安检，必须在鹰眼的扫描盲区里移动。"Echo飘到安检门旁边，投影被鹰眼的红光切割成碎片，"但鹰眼会转动——它们的扫描区是固定的，只要我们在每个扫描区的边缘放置干扰器，就能让鹰眼以为那里是安全的。"

"用最少的干扰器。"你说，"覆盖所有鹰眼的扫描区。"

CC从背包里掏出干扰器——只有五个。她数了数："不够每个鹰眼一个。"

"不需要每个一个。"你蹲下来，在终端上标出十二个鹰眼的扫描区——每个区有一个左边界和一个右边界。"按右边界排序。每次在最右边的边界放一个干扰器，能覆盖所有左边界小于该点的扫描区。"

"就像……"CC想了想，"用一发脉冲扫一群目标，扫最右边那个，左边的也吓跑了。"

"差不多。"

你开始写。十二个扫描区按右端点排好，然后从最左边开始扫描——遇到没被覆盖的区域，就在它的最右边缘放一个干扰器。这个点会覆盖所有与它相交的区域。

屏幕上跳出了结果：三个干扰器就够了。

CC把三个干扰器拍在指定位置。球形的鹰眼转动到那些位置时，扫描区里出现了短暂的信号空白——就像人眨眼时的瞬间盲区。

"走。"CC说，"趁它们眨眼。"

题目描述

$n$ 个区间，每个区间 $[l_i, r_i]$。选最少数量的点，使得每个区间内至少有一个点。

输入格式

$n$。然后 $n$ 行，每行 $l_i, r_i$。

输出格式

最少点数。

输入样例

3 2
1 2
-3 1
2 1

输出样例

Case 1: 2

提示

• 按右端点排序。
• 从第一个区间开始，在其右端点放一个点，覆盖所有与该点相交的区间。
• 然后跳到下一个未被覆盖的区间，重复。

你们穿过安检门，进入G-14数据枢纽的内部。走廊两侧是一排排数据舱，每个舱里都有休眠的服务器。Echo的投影在舱壁之间穿行，像一道光在通道中穿行。

"前面是资源调度区。"她说，"Zero把数据舱分成多个时段出租——每个时段有一个开始时间和结束时间。我们要预订尽可能多的不重叠时段，用来上传我的碎片数据。"

"不能重叠？"CC问。

"不能。一个时段内只能有一个数据流。"

"那就挑结束最早的先订。"CC说，"结束得早，后面才留得多。"

"对。"你说，"按结束时间排好，每次选结束最早的、且不与前一个重叠的时段。"