Avtobus marşrutları
Bir ölkədə, düzbucaqlı formada olan şəhərlərarası magistral yollar şəbəkəsi sadə bir quruluşa malikdir. Hər bir magistral, ölkənin sərhədinin əks tərəflərini birləşdirərək, ya şimaldan cənuba, ya da qərbdən şərqə doğru uzanan düz bir xəttdir. Bəzi magistralların kəsişdiyi yerlərdə şəhərlər yerləşir, lakin heç bir iki şəhər eyni magistral üzərində yerləşmir.
Ölkə kifayət qədər zəngin idi və buna görə də büdcə vəsaitlərini çox düşünmədən xərcləyirdi. Məsələn, hər bir şəhər cütü arasında birbaşa avtobus marşrutu mövcud idi ki, bu da sərnişinləri bir şəhərdən digərinə ən qısa yolla dayanmadan daşıyırdı.
Lakin, növbəti ilin büdcəsini planlaşdırarkən, şəhərlərarası daşımaların gəlirinin onların xidmət xərclərindən dəfələrlə az olduğu məlum oldu. Buna görə də, marşrutların sayını maksimum dərəcədə azaltmaq qərarı verildi. Bununla belə, xalqın narazılığını önləmək üçün, istənilən iki şəhər arasında qət edilməli olan məsafənin əvvəlki kimi minimal qalması təmin edilməli idi.
Giriş verilənləri
Birinci sətirdə bir natural ədəd N – şəhərlərin sayı verilir, 2 ≤ N ≤ 10000.
Sonra N sətir gəlir, hər biri iki tam qeyri-mənfi ədəd x_i, y_i – şəhərlərin yerləşdiyi magistralların nömrələri (x_i – şimaldan cənuba gedən magistralın nömrəsi, y_i – qərbdən şərqə gedən magistralın nömrəsi).
Hər istiqamətdə magistrallar ardıcıl olaraq 0 ilə 1000000 arasında nömrələnir. Şimaldan cənuba gedən magistrallar qərbdən şərqə, qərbdən şərqə gedən magistrallar isə şimaldan cənuba nömrələnir.
Çıxış verilənləri
Birinci sətirdə bir tam ədəd P – saxlanmalı olan minimal avtobus marşrutlarının sayı verilməlidir.