Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: karalyste.in

Rezultatų failas: karalyste.out

Jei norite pateikti savo sprendimą - prisijunkite.

Karalystės keliai

Karalystėje yra n miestų, kuriuos jungia n-1 kelių taip, kad yra lygiai vienas būdas nukeliauti nuo vieno miesto iki kito.

Karalius yra užsiėmęs žmogus ir dažnai keliauja iš miesto į miestą. Deja, vienos kelionės metu, vienas kelias buvo smarkiai sugadintas ir turėjo būti taisomas. Dėl to Karalius negalėjo laiku būti reikiamame mieste.

Po šio įvykio Karalius nusprendė pagerinti kelių sistemos patikimumą. Nuspręsta, kad pagerinta kelių sistema atlaikys vieną sugadintą kelią, t.y., visada bus bent vienas kelias iš bet kurio miesto į bet kurį kitą, net kai vienas Karalystės kelias yra sugadintas. Kaip visada, biudžetas yra ribotas, todėl reikia kiek įmanoma sumažinti naujų kelių kiekį.

Pradiniai duomenys

Pirmoje eilutėje yra vienas sveikasis skaičius n (2\\len\\le10^5), Karalystės miestų kiekis. Tolesnėse n-1 eilutėse yra po du sveikuosius skaičius u_i ir v_i (1\\leu_i,v_i\\len), i-uoju keliu sujungtų miestų numeriai.

Rezultatai

Pirmoje eilutėje turi būti vienas skaičius k, naujų kelių kiekis. Tolesnėse k eilutėse turi būti po du skaičius a_i ir b_i (1\\lea_i,b_i\\len), i-uoju nauju keliu sujungiamų miestų numeriai.

Gali būti keletas optimalių sprendimų. Tiks bet kuris.

Pavyzdžiai

Duomenys Rezultatai 
5
1 2
2 3
3 4
3 5
 
2
1 4
4 5
 
4
1 2
1 3
1 4
 
2
3 2
1 4