Zadanie

Fakt veľa mostov

Počet bodov: 45

Po poklese cien stavebných materiálov KMS (Komisia Mostového Stavania) rozhodla, že sa budú stavať mosty. Fakt veľa mostov.

Navrhli \(N\) mostov, ktoré môžu postaviť cez miestny potok. Potok tečie zľava doprava a na jeho hornom aj dolnom brehu je \(N\) križovatiek. Každý most je určený tým, ktoré dve križovatky (jednu na dolnom a jednu na hornom brehu) spája. Každá križovatka je vhodná na spojenie s práve jednou križovatkou na opačnom brehu.

Problém však nastáva, keď sa mosty majú križovať - teda ak by sa mal postaviť most medzi križovatkami \(a\) a \(b\), a zároveň \(x\) a \(y\), pričom \(a < b\) a zároveň \(x > y\). Napríklad most medzi \(3\) a \(8\) by sa križoval s mostom medzi \(4\) a \(5\).

KMS si za návrhmi pevne stojí. Zistite, koľko najviac mostov vedia postaviť, aby sa žiadne z nich nekrižovali.

Vstup a výstup

V prvom riadku je číslo \(N\) - počet návrhov na mosty, ako aj počet križovatiek na hornom a dolnom brehu potoka.

V každom z ďalších \(N\) riadkov sú dve čísla \(a\) a \(b\) - návrh na postavenie mosta medzi križovatkou \(a\) na dolnom brehu a križovatkou \(b\) na hornom brehu. Križovatky sú očíslované od \(1\) po \(N\) zľava doprava. Každé číslo od \(1\) po \(N\) sa objaví práve raz ako \(a\) a práve raz ako \(b\).

Vypíšte jedno číslo - najväčší počet mostov, ktoré sa dajú naraz postaviť bez toho, aby sa križovali.

V prvej sade platí \(1 \leq N \leq 10\).

V druhej sade platí \(1 \leq N \leq 1\,000\).

Príklady

Input:

9
1 1
3 2
2 3
4 9
5 6
7 8
6 7
8 5
9 4

Output:

5

Vieme postaviť napríklad prvý, druhý, piaty, šiesty a siedmy most. Nedá sa postaviť šesť mostov bez toho, aby sa niektoré križovali.