Avtobus marşrutları#1424
Bir düzbucaqlı şəklə malik ölkədə şəhərlərarası avtomobil yolları şəbəkəsi sadədir. Hər bir avtomobil yolu ya yalnız şimaldan cənuba, ya da yalnız qərbdən şərqə doğru uzanan düz xətdir və ölkənin əks sərhədlərini birləşdirir. Şəhərlər bəzi avtomobil yollarının kəsişməsində yerləşir və heç bir ikisi eyni avtomobil yolunda deyil.
Ölkə bir vaxtlar zəngin idi və büdcəsini olduqca laqeyd xərcləyirdi. Məsələn, hər iki şəhər cütü arasında birbaşa avtobus marşrutu vardı və sərnişinlər bir şəhərdən digərinə ən qısa yolla, dayanacaq etmədən gedə bilirdilər.
Lakin növbəti ilin büdcəsi planlaşdırılanda məlum oldu ki, şəhərlərarası nəqliyyatdan gələn gəlir belə şəbəkənin saxlanılması xərclərindən xeyli azdır. Buna görə mümkün qədər çox marşrutun ləğv olunmasına qərar verildi. Cəmiyyətin narazılığının qarşısını almaq üçün isə tələb edildi ki, istənilən iki şəhər arasındakı ən qısa səyahət məsafəsi dəyişməz qalsın.
Birinci sətirdə bir təbii ədəd verilir — şəhərlərin sayı (2 \leq N \leq 10000).
Növbəti sətrin hər birində iki qeyri-mənfi tam ədəd x_i, y_i verilir — hər şəhərin yerləşdiyi magistral yolların nömrələri (x_i — şimal-cənub istiqamətində olan yolun nömrəsi, y_i — qərb-şərq istiqamətində olan yolun nömrəsi).
Hər bir istiqamətdə magistral yollar ardıcıl şəkildə -dan -ə kimi nömrələnib. Şimal-cənub yolları qərbdən şərqə doğru, qərb-şərq yolları isə şimaldan cənuba doğru nömrələnib.
Birinci sətirdə bir tam ədəd çap edin — saxlanılmalı olan minimum avtobus marşrutlarının sayı.
Nümunə 1