Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: pcb.in

Rezultatų failas: pcb.out

Jei norite pateikti savo sprendimą - prisijunkite.

Spausdintinė schemos plokštė (BOI 2010)

Spausdintinėje schemos plokštėje laidai yra išdėstomi nelaidžioje medžiagoje. Kadangi tame pačiame sluoksnyje esantys laidai negali kirstis, naudojamos plokštės turinčios keletą nelaidžia medžiaga atskirtų sluoksnių. Daugiau sluoksnių turinčios plokštės yra brangesnės, todėl gamintojai bando paskirstyti reikalingus laidus į sluoksnius taip, kad reikėtų kuo mažiau sluoksnių. Šioje užduotyje tirsime plokštes, kuriose kiekvienas laidas jungia du priešingose plokštės pusėse esančius įvesties-išvesties prievadus, ir stengsimės sumažinti tokios plokštės kainą. Kaip pavyzdį, panagrinėkime schemą kairiajame paveiksle. Jei vienas laidas turi sujungti A ir B, o kitas C ir D, tokia plokštė gali turėti vieną sluoksnį, kaip parodyta viduriniajame paveiksle. Tačiau laidas, jungiantis A ir C, bei laidas, jungiantis B ir D, negali būti tame pačiame sluoksnyje, kaip parodyta dešiniajame paveiksle.

Užduotis

Parašykite programą, kuri pagal N laidų prievadų vietas W\\timesH dydžio lentoje nustatytų, kiek mažiausiai sluoksnių reikia, norint sutalpinti visus laidus. Laikykite, kad laidų plotis yra labai mažas lyginant su atstumu tarp prievadų. Tai reiškia, kad tarp bet kurių dviejų laidų visada yra vietos trečiam.

Pradiniai duomenys

Pirmoje eilutėje įrašytas laidų kiekis N(1\\leqN\\leq10^5). Kiekvienoje tolesnių N eilučių yra du tarpu atskirti sveikieji skaičiai, X_{i1} ir X_{i2} (0\\leqX_{ij}\\leq10^6). Jie reiškia, kad i-asis laidas turi jungti prievadus, esančius taškuose (X_{i1},0) ir (X_{i2},H). Visi 2\\timesN prievadai yra skirtingose vietose.

Rezultatai

Vienintelėje eilutėje turi būti vienas sveikasis skaičius - mažiausias sluoksnių, reikalingų sutalpinti visus laidus, kiekis.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
1
5 5
 
1
 
5
3 0
2 2
4 4
1 3
0 1
 
3