SPOJ in Armenian

Էլեկտրոնային սխեմաներում, հաղորդիչ լարերը անց են կացվում ոչ հաղորդիչ հիմքի վրա, որոնք, սովորաբար, պատրաստում են մի քանի շերտից, որպեսզի լարերը չհատվեն և կարճ միացում չառաջանա։ Սակայն, որքան շերտերը շատ են, այնքան էլեկտրոնային սխեման ավելի թանկ է։ Դրա համար արտադրողները լարանցումները շերտերում ձգտում են այնպես կազմակերպել, որ շերտերի քանակը մինիմալ լինի։

Այս խնդրում կդիտարկենք այնպիսի հիմքեր, որոնցում յուրաքանչյուր հաղորդալար պետք է միացնի հիմքի երկու հակառակ եզրերում գտնվող երկու պորտեր։ Միացումները պետք է այնպես անել, որ ընդհանուր սխեմայի արժեքը մինիմալ լինի։

Դիտարկենք, օրինակ, ձախ կողմի նկարում պատկերված հիմքը։ Եթե մի հաղորդալարով միացվեն A և B պորտերը, և մեկ այլ հաղորդալարով D և C պորտերը, ապա դա կարելի է անել մի շերտի վրա, ինչպես ցույց է տրված մեջտեղի նկարում։ Բայց, եթե պետք է միացնել A-ն C-ին, իսկ D-ն B-ին, ապա դա հնարավոր չէ անել մի շերտում, ինչպես ցույց է տրված աջ կողմի նկարում։

Պահանջվում է գրել ծրագիր, որը հաշվի, թե  W × H  չափի հիմքի վրա տրված ծայրակետերով N լարանցումներ կազմակերպելու համար առնվազն քանի շերտ է անհրաժեշտ։

 Կարող եք ենթադրել, որ հաղորդալարերի լայնությունը անհամեմատ փոքր է պորտերի միջև հեռավորությունների նկատմամբ։ Այնպես որ, ցանկացած երկու հաղորդալարերի միջև միշտ երրորդի համար տեղ կա։

Մուտքը

Առաջին տողում տրված է միացումների N (1 ≤ N ≤ 10⁵) քանակը։ Հաջորդ N տողերից յուրաքանչյուրում տրված են, իրարից մեկ բացակով անջատված, երկու ամբողջ Xi1 և Xi2 (0 ≤ Xij ≤ 10⁶) թվեր, նշանակում է i-րդ հաղորդալարը պետք է միացնի (Xi1, 0) և (Xi2,H) կետերը։ Համարել, որ մուտքում տրված բոլոր  2 · N ծայրակետերը տարբեր են։

Ելքը

Ելքում պետք է արտածել մի ամբողջ թիվ՝ պահանջվող լարանցումները կազմակերպելու համար մինիմալ շերտերի քանակը։

Օրինակներ

Մուտքը.
2
1 1
3 3

Ելքը.
1

Մուտքը.
2
1 3
3 1

Ելքը.
2