提示: 欢迎访问OurACM平台。
Problem 1506 堆箱子

Accept: 404    Submit: 1482
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

ACM小组搬实验室了,ACM小组的成员决定把实验室中的物品先放入n个箱子,然后把这些箱子叠放成几堆。每个箱子的长宽由一个二元组表示(注意:l与w的大小关系不确定,并且它们是有序二元组,它们的位置不能交换)。出于稳定性的考虑,一个长宽为的箱子能堆放在另一个长宽为< l',w' >的箱子上,则需满足l<=l',w<=w'.

由于室内面积有限,所以ACM小组的成员希望这些箱子分成的堆数最少。

比如:有5个箱子,它们的长宽分别是<9,4>,<2,5>,<1,2>,<5,3>,<4,1>,则可以把它们堆放成两堆,

 
<9,4>,<5,3>,<4,1>
<2,5>,<1,2>

Input

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

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

Output

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

Sample Input

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

Sample Output

2 1 3

Source

FOJ月赛-2007年5月

Submit  Back  Status  Discuss