B24 - Many Boxes Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の箱があります。i 個目の箱の縦の長さは X_i であり、横の長さは Y_i です。
以下の 2 つの条件両方を満たすとき、箱 A を箱 B の中に入れることができます。

  • (箱 A の縦の長さ) < (箱 B の縦の長さ)
  • (箱 A の横の長さ) < (箱 B の横の長さ)

箱は最大で何重にすることができますか。
ただし、箱を回転させて縦の長さと横の長さを逆にする操作はできないものとします。

制約

  • 1 \leq N \leq 100000
  • 1 \leq X_i \leq 500000
  • 1 \leq Y_i \leq 500000
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。 

N
X_1 Y_1
X_2 Y_2
 :
X_N Y_N

出力

答えを整数で出力してください。

入力例 1

5
30 50
10 30
40 10
50 20
40 60

出力例 1

3

外側から順に「箱 5, 1, 2」と置くことで、箱を 3 重にすることができます。

入力例 2

9
10 90
20 80
30 70
40 60
50 50
60 40
70 30
80 20
90 10

出力例 2

1