AT_abc038_d.[ABC038D] プレゼント

高桥君需要准备一份礼物。礼物的内容已经确定，现在只需要准备一个用来装礼物的盒子。高桥君可以使用 $N$ 个盒子，第 $i$ 个盒子的尺寸为高 $h_i$ cm × 宽 $w_i$ cm。

高桥君认为，如果礼物能被装在更多层盒子里会更有趣，因此他打算尽可能多地将盒子套在一起，并把礼物放在最内层的盒子里。一个盒子只能被放入高和宽都严格大于它的盒子中。另外，每个盒子最多只能再套一个盒子。

请你求出，最多可以将多少个盒子套在一起来装礼物。

输入以如下格式从标准输入读入。

$N$
$w_1$ $h_1$
$w_2$ $h_2$
$\vdots$
$w_N$ $h_N$

请输出能用来包裹礼物的盒子的最大层数，输出一个整数。

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq h_i \leq 10^5$
• $1 \leq w_i \leq 10^5$

部分得分

• 如果能通过所有 $N \leq 1,000$ 的测试用例，可以获得 $30$ 分。

样例解释 1

可以依次用第 $1$、$3$、$2$ 个盒子从外到内包裹礼物。

样例解释 2

注意，盒子不能旋转 $90$ 度。另外，不能将高或宽相等的盒子套在一起。

由 ChatGPT 4.1 翻译