Uçuş planlaşdırılması
NCPC Hava Yolları dünyada n şəhər arasında uçuşlar həyata keçirir, bu şəhərlər 1-dən n-ə qədər nömrələnmişdir. Lakin şirkətin yalnız n - 1 fərqli reysi (hər iki istiqamətdə) mövcuddur, bu da o deməkdir ki, hər hansı iki şəhər arasında səyahət etmək üçün bir neçə reysdən istifadə etmək lazımdır. Menecment, hər iki şəhər arasında səyahət imkanının olduğuna əmin olmaq üçün sərnişinlərin yalnız bir hava yolu ilə istifadə edərək hərəkət edə biləcəyi dəqiq bir reys dəstini təmin edir.
Son zamanlarda, NCPC Hava Yollarının tez-tez uçan sərnişinləri, çox sayda reys dəyişdirməli olduqlarından şikayət edirlər ki, bu da onları son təyinat nöqtəsinə çatdırır. Müştərilərini itirmək istəməyən və reyslərinin rahatlığını qorumaq istəyən NCPC Hava Yolları, bir reysi ləğv edib başqa bir reyslə əvəz etməyə qərar verib. Hava yoluna, bir reysi ləğv edərək və NCPC Hava Yollarının xidmət etdiyi şəhər cütləri arasında səyahət edərkən sərnişinin reys dəyişdirmə sayını minimuma endirmək üçün yeni bir reysi əlavə etməkdə kömək edəcək bir proqram yazın.
Giriş məlumatları həmişə reys dəyişdirmə sayını yaxşılaşdırmağın mümkün olduğu şəkildə veriləcəkdir.
Giriş məlumatları
Birinci sətir NCPC Hava Yollarında n şəhərin sayını (4 ≤ n ≤ 2500) ehtiva edir. Sonrakı n - 1 sətir reysləri təsvir edir. Hər bir reys şəhər cütü a və b (1 ≤ a, b ≤ n) ilə verilir.
Çıxış məlumatları
Üç sətir çıxış edilməlidir. Birinci sətir, reys dəyişdirmə sayının minimuma endirilməsi üçün səyahət edərkən şəhər cütləri arasında dəyişdirilməli olan reyslərin ən az sayını ehtiva edir. İkinci sətir, ləğv ediləcək reysin şəhər nömrələrini ehtiva edir. Üçüncü sətir, yeni reysin əlavə ediləcəyi şəhər nömrələrini ehtiva edir.
Əgər bir neçə həll yolu varsa, istənilən birini çıxış edin.