Witam,
Mam takie o to zadanie:
Dawno, dawno temu był sobie kraj mlekiem i miodem płynacy z rozkoszami, jakich nikt nigdy nie zaznał, gdzie problemy NP-zupełne rozwiazywało sie w czasie liniowym. Kraj ten zwał sie Bajtocja. Bajtocja składa sie z N miast połaczonych siecia dwukierunkowych dróg, w taki sposób, ze miedzy kazdymi dwoma miastami mozna przejechac tylko na jeden sposób bez zawracania.
Król Bajtazar, aby poprawic humor sobie i swoim poddanym postanowił odnowic najwieksza ilosc dróg w Bajtocji. Niestety, nie pomyslał o tym, ze aby odnowic droge, nalezy najpierw ja zamknac. Poddani oburzyli sie, ze siec dróg bedzie zamknieta. Król bojac sie o swoja popularnosc ogłosił, ze dla kazdego miasta zamknie maksymalnie jedna droge, która przechodzi przez to miasto. Jednoczesnie jednak chce dokonac renowacji najwiekszej liczby dróg. Pomóz mu!
Napisz program, który: wczyta ilosc miast w Bajtocji oraz opis dróg miedzy miastami, wyznaczy maksymalna liczbe dróg, która mozna poddac naprawom i wypisze wynik na standardowe wyjscie.
WEJSCIE
W pierwszym wierszu znajduje sie jedna liczba naturalna N , okreslajaca liczbe miast. W kolejnych N − 1 wierszach znajduje sie opis sieci dróg w Bajtocji. Opis kazdej drogi składa sie z dwóch liczb naturalnych u i v, oddzielonych pojedynczym odstepem i okreslajacych numery miast, które połaczone sa dana droga.
Miasta numerowane sa kolejnymi liczbami naturalnymi od 1 do N (włacznie).
WYJSCIE
Twój program powinien wypisac na wyjscie dokładnie jedna liczbe całkowita — maksymalna liczbe dróg, które zostana poddane naprawom.
OGRANICZENIA
1 <= N <= 200 000.
PRZYKŁAD
Wejscie
8
1 2
2 3
2 4
3 7
4 5
4 6
6 8
Wyjscie
4
Udalo mi sie dojsc tylko do tego, ze ten graf da sie przedstawic jako drzewo.
Z gory dziekuje za wszystkie odpowiedzi.