题目描述

给定 $n$ 个矩形，其中第 $i$ 个矩形的长为 $a_i$，宽为 $b_i$。

如果一个矩形的长不超过另一个矩形的长，并且它的宽也不超过另一个矩形的宽，那么这个矩形可以嵌在另一个矩形里。矩形之间可以多层嵌套，请计算这些矩形最多能嵌套多少层。

每个矩形的长和宽不可互换。

输入格式

第一行，一个整数 $n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，表示第 $i$ 个矩形的长和宽。

输出格式

输出一个整数，表示矩形嵌套的最大层数。

输入输出样例

输入 #1

4
3 4
1 2
2 3
2 5

输出 #1

3

说明/提示

$(1,2)$ 可以套在 $(2,3)$ 中，$(2,3)$ 可以套在 $(3,4)$ 中，因此最多嵌套 $3$ 层。

数据范围

• 对于 $30\%$ 的数据，$1\le n\le 15$；
• 对于 $60\%$ 的数据，$1\le n\le 5000$；
• 对于全部数据，$1\le n\le 200000$，$1\le a_i,b_i\le 10^9$。

4
3 4
1 2
2 3
2 5

3

10
675875471 240232859
356625982 716143802
320163299 782097774
501969016 141767771
983613338 534790135
605605996 991934056
598553584 664846272
632214804 653461496
989203834 647169606
647463339 561142949

4

13
598305770 409026366
546473843 637005578
26701210 112122870
66326876 782615756
639625951 749434055
47600191 879699537
799467909 591580007
426784272 789240294
630748811 112566607
357934618 123022810
383145103 776705230
571320890 864604092
358152068 6957234

5