题目描述

$Bob$ 正在玩“套环”游戏，初始时系统给定 $n$ 个矩形环，第 $i$ 个矩形环宽 $w_i$ ，高 $h_i$ 。

当两个矩形环 $i,j$ ，满足 $w_i<w_j,h_i<h_j$ 时，可以将环 $i$ 放入环 $j$ 中，即“大的套小的”。

现在 $Bob$ 可以从中选择若干个环，“大的套小的”形成“套环”， 请帮助 $Bob$ 选出最多的环，组成“套环”。

注意：矩形环不能旋转。

输入格式

输入格式如下：

$n$

$w_1$ $h_1$

$\dots$

$w_n$ $h_n$

输出格式

一个整数，最长的“套环”数量。

5
1 2
2 3
3 4
4 6
3 4

4

样例1解释

可以选择第 1,2,3,4 个环组成套环，数量最多就是 4 ，没有其他更优方案。

5
2 1
2 2
2 3
2 4
2 5

1

20
2 19
20 10
2 5
10 17
5 14
18 7
17 11
17 15
13 1
16 5
17 15
12 10
4 11
13 1
20 11
4 9
16 13
13 17
6 6
2 7

5

数据规模与约定

所有数据满足：$1\le n \le 2\times 10^5, 1\le w_i,h_i \le 2 \times 10^5$

$subtask1$ : $1 \le n \le 10$ , $10$ 分

$subtask2$ : $1 \le n \le 10^4$ , $30$ 分

$subtask3$ : $1 \le n \le 2 \times 10^5$ , $60$ 分