Uçuş planlaşdırılması#548
NCPC Airways şəhər arasında uçuşlar həyata keçirir, şəhərlər -dən -ə kimi nömrələnmişdir. Lakin hava yolu şirkətinin cəmi n - 1 fərqli uçuşu var (hər iki istiqamətdə işləyir), bu da o deməkdir ki, istənilən iki şəhər arasında səyahət etmək üçün bir neçə uçuşdan istifadə etmək lazım ola bilər. Rəhbərlik təmin edib ki, istənilən şəhər cütü arasında yalnız bir yol mövcuddur (əgər yalnız NCPC Airways-dən istifadə etsəniz).
Son zamanlar, daimi sərnişinlər şikayət edirlər ki, təyinat nöqtəsinə çatmaq üçün çox tez-tez reys dəyişməli olurlar. Müştərilərin qayğısına qalan və rahat keçidləri qoruyub saxlamaq istəyən NCPC Airways qərara alıb ki, bir uçuşu ləğv edib yerinə yeni bir uçuş əlavə etsin. Hava yolu şirkətinə kömək etmək üçün bir proqram yazın ki, hansı uçuşu ləğv etməli və hansı şəhərlər arasında yeni uçuş əlavə etməli olduğunu müəyyən etsin ki, istənilən iki şəhər arasında lazım olan maksimum reys dəyişmələrinin sayı mümkün qədər az olsun.
Giriş informasiyası həmişə belədir ki, tələb olunan maksimum reys dəyişmələrinin sayını yaxşılaşdırmaq mümkündür.
Birinci sətirdə (4 \le n \le 2500) — şəhərlərin sayı verilir. Növbəti n-1 sətrin hər birində iki şəhərin nömrəsi və (1 \le a, b \le n) verilir və bu, onların arasında uçuşun olduğunu göstərir.
Üç sətir çap edin. Birinci sətirdə, bir uçuşu dəyişdikdən sonra istənilən şəhər cütü üçün lazım olan maksimum uçuş sayının mümkün olan minimumunu çap edin. İkinci sətirdə, ləğv ediləcək uçuşun olduğu iki şəhərin nömrəsini çap edin. Üçüncü sətirdə, əlavə ediləcək yeni uçuşun iki şəhərinin nömrəsini çap edin.
Əgər bir neçə optimal həll varsa, istənilənini çap edə bilərsiniz.
Nümunə 1