配点 : 600 点
問題文
N 矩形,并且矩形 i 的宽度和高度是 A_i, B_i 。
Snuke 可以选择其中一些矩形并按顺序堆叠它们。 1 我正在尝试制作两种图案。 这时, 放置的第j\ (2 \leq j) 个矩形必须满足以下条件。 完全包含在
- j-1 放置的矩形内。 放置
- j-1 的矩形的边不得相互接触。
- 每边都是 它必须平行于 j-1 放置的矩形的一侧。
放置矩形时,请您可以交换宽度和高度。。另外,无论矩形的数量如何,都可以自由确定矩形的放置顺序。
Snuke 可以制作多少个重叠的矩形?
制約
输入满足以下条件。
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i,B_i \leq 10^9
- 所有输入值均为整数
入力
输入将以以下形式从标准输入给出。
N A_1 B_1 A_2 B_2 : A_N B_N
出力
打印 Snuke 可以重叠的最大矩形数。 如果按照如图所示的顺序排列
入力例 1
4 3 4 1 5 5 5 3 1
出力例 1
3
長方形 3、長方形 1、長方形 4 , 3 您可以重叠两个矩形。 请注意,您可以交换矩形的宽度和高度。
入力例 2
3 1000000000 1000000000 1000000000 1000000000 1000000000 1
出力例 2
1
请注意,边缘不得相互接触。