Problem G: Yu-kun Likes Building Block

Background

会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君はプログラミングと同じくらい長方形の積み木が大好きだ。 そんなゆう君は、最近積み木で山を作る遊びに熱中している。

今日もゆう君は山を作って遊んでいたのだが、持っている積み木で沢山の山を作る事は簡単なので、今日は全ての積み木を使って出来る山の数を最小化しようと考えた。 そこでゆう君は、実際に全ての積み木を使って山を作った後、本当にその山の数が最小になっているのかどうかを確かめるために、プログラムを書く事にした。

Problem

ゆう君が持っている積み木の数と積み木の情報が与えられるので、そこから作る事のできる山の数の最小値を求めよ。

積み木は平面上の長方形として表され、その長方形の縦と横の長さが積み木の情報として与えられる ( 積み木の高さは考慮しない )。

山は積み木の上に０個以上の積み木が積み重なったものである。 ただし、積み木の上に別の積み木を重ねるためには、上になる積み木の縦、横の長さはそれぞれ下となる積み木の縦、横の長さ未満でなければならない。 １つの積み木の上に直接置くことができる積み木は1つまでである。

積み木を置く際に、2つの積み木の縦、横はそれぞれ平行でなければならない（斜めの状態で重ねることは許されない）。 積み木を回転させ縦と横を交換しても良い。

例えば、図1のような状態について考える。長方形は積み木を表し、その左にある数字は積み木の縦の長さを、下にある数字は横の長さを、長方形の中の左上の数字は積み木の番号を表している。 最初の状態では５つの山がある。

図1のように重ねていく事で、最終的に山の数を２つまで減らすことができる。

図1

Input

N
w0 h0
w1 h1
...
wN-1 hN-1

入力は全て整数である。

Nは積み木の数を表す。 ( 1 ≤ N ≤ 100 )

w_i,h_iはそれぞれ積み木の横、縦の長さを表す。( 1 ≤ w_i,h_i ≤ 10⁹ )

Output

全ての積み木を使ってできる山の数の最小値を１行に出力せよ。

Sample Input 1

3
1 1
2 2
3 3

Sample Output 1

1

Sample Input 2

5
2 3
3 5
1 2
1 4
3 5

Sample Output 2

2

Sample Input 3

5
1 5
2 4
3 3
4 2
5 1

Sample Output 3

5

Sample Input 4

10
5 11
12 12
4 14
22 12
11 13
3 3
3 3
12 5
55 55
1 1

Sample Output 4

3