题目描述

现在有一堆箱子，每个箱子长为ai，宽为bi, 现在需要把这些箱子叠放成几堆。每个箱子的长宽由一个二元组表示(ai,bi);出于稳定性的考虑，一个长宽为(ai,bi)的箱子能堆放在另一个长宽为（am,bm）的箱子上，则需满足ai<=am,bi<=bm;现需要满足最少堆数。

输入要求

本题有多组输入数据，你必须处理到EOF为止

第一行是一个正整数n (1<=n<=100,000)。接下来有n行，每行有两个正整数li,wi(li,wi <= 1,000,000)，分别表示第i个箱子的长宽.

输出要求

输出这些箱子分成的最少堆数.

输入样例

5
4 9
5 2
2 1
3 5
1 4
3
2 2
1 1
2 2
3
1 3
2 2
3 1

输出样例

2
1
3

提示

来源

NBU OJ