题目描述

考虑如下的一个简单问题：

你有 $n$ 个线段在数轴上，你要选出尽量多的线段，使它们两两不交。

我知道你一定会做，但你需要解决这个：

你有 $n$ 个线段在数轴上，你要选出尽量多的线段对 $(u_i,v_i)_{i=1}^k$，即最大化 $k$。

满足 $k+1$ 个要求：

• $u_1,u_2,\cdots,u_k$ 两两不交。
• $v_1,u_2,u_3,\cdots,u_k$ 两两不交。
• $u_1,v_2,u_3,u_4,\cdots,u_k$ 两两不交。
• $\cdots$
• $u_1,u_2,\cdots,u_{k-1},v_k$ 两两不交。

其中 $\forall i$，$u_i$ 与 $v_i$ 不能相同。

输入格式

第一行一个正整数 $n(n\geq2)$。

接下来 $n$ 行每行两个正整数 $a_i,b_i(1\leq a_i<b_i\leq10^9)$，表示一个线段的两个端点。

两个线段 $i,j$ 不交当且仅当 $b_i\leq a_j$ 或 $b_j\leq a_i$。

输出格式

第一行一个正整数 $k$。

样例 #1

样例输入 #1

8
1 5
3 10
4 8
9 12
11 16
14 15
20 22
15 21

样例输出 #1

3