Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Poravimas

Jums duotas medis, turintis N viršūnių. Jūsų užduotis - surasti, kiek daugiausiai medžio briaunų įmanoma parinkti taip, kad nė viena pora briaunų neturėtų bendrų viršūnių.

Pavyzdžiui, žemiau pateiktame medyje paryškintos tos briaunos, kurios tarpusavyje neturi bendrų viršūnių, o pats briaunų skaičius yra maksimalus. Taigi, šiuo atveju atsakymas būtų 7, nes tiek briaunų buvo parinkta.

paaiškinimas

Pradiniai duomenys

Pirmoje eilutėje pateiktas vienas sveikasis skaičius N - viršūnių skaičius (1\\leqN\\leq2\\cdotp10^5).

Toliau seka N-1 eilučių. i-ojoje iš jų pateikti du sveikieji skaičiai u ir v, reiškiantys, kad viršūnes u ir v jungia briauna (1\\lequ,v\\leqN).

Rezultatai

Jūsų programa turi išvesti vieną sveikąjį skaičių - kiek daugiausiai briaunų galima parinkti, kad jos tarpusavyje nesiliestų.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
15
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10
5 11
6 12
7 13
8 14
9 15
 
7
 Pavyzdys atitinka sąlygoje pateiktą paveiksliuką 
6
1 2
1 3
1 4
4 5
4 6
 
2
 Vienas iš galimų būdų parinkti briaunas:
pavyzdys