AtCoder Beginner Contest 038

D - プレゼント


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋くんはプレゼントを用意することになりました。プレゼントの中身はすでに決まり、あとはプレゼントを入れる箱を用意するだけです。 高橋くんが使える箱はN個あり、i番目の箱は縦h_icm×横w_icmのサイズです。

プレゼントがより多くの箱に入っていたほうが面白いと考えた高橋くんは、なるべく多くの箱を入れ子にし、最も内側の箱にプレゼントを入れることにしました。 ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができます。また、ある箱は1つまでしか他の箱を入れることはできません。

プレゼントを入れる箱を最大で何重の入れ子にできるか答えてください。


制約

  • 1≦N≦10^5
  • 1≦h_i≦10^5
  • 1≦w_i≦10^5

部分点

  • N ≦ 1,000 を満たすテストケース全てに正解した場合、部分点として30点が与えられる。

入力

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

N
w_1 h_1
w_2 h_2
:
w_N h_N

出力

プレゼントを包む箱の数の最大値を 1 行に出力せよ。


入力例1

3
3 3
1 1
2 2

出力例1

3

外側の箱から順に、1, 3, 2番目の箱でプレゼントを包むことができます。


入力例2

2
4 5
4 3

出力例2

1

箱を90度回転することはできないことに注意してください。また、ある箱を縦または横の長さが等しい箱に入れることはできません。


入力例3

4
2 5
3 3
4 5
6 6

出力例3

3

入力例4

5
8 8
5 3
2 2
4 2
2 1

出力例4

4

Submit提出する