Ach, bajtockie góry! Ostoja dzikiej przyrody i nieskalanego piękna; tajemnicze, groźne, a jednocześnie urzekająco piękne. Bajtocka Administracja Terenów Ogólnie Nierównych (BATON) zajmuje się, miedzy innymi, zarządzaniem górskim parkiem krajobrazowym - diamentem w koronie Gór Bajtockich. W parku tym znajdują się dwukierunkowe ścieżki, które przecinają się jedynie w punktach widokowych oraz układają się w taki sposób, że między dowolnymi dwoma punktami istnieje dokładnie jeden sposób przejścia (być może odwiedzając po drodze inne punkty widokowe). Dzięki temu turyści nie gubią się w parku.
BATON zastanawia się, jak poprowadzić szlaki turystyczne. Z jednej strony muszą one pokrywać wszystkie ścieżki (tzn. każda ścieżka musi należeć do przynajmniej jednego szlaku), w przeciwnym wypadku park szybko zarósłby chwastami. Jednak z drugiej strony szlaków musi być jak najmniej, aby nie dezorientować turystów. Jeden szlak może przechodzić przez każdy punkt widokowy conajwyżej raz (aby nie znudzić turystów). Pomóż BATONowi - dla danego opisu parku krajobrazowego wyznacz minimalną liczbę szlaków turystycznych niezbędnych do pokrycia wszystkich ścieżek!
W pierwszej linii wejścia dana jest liczba n (2 ≤ n ≤ 1 000 000), oznaczająca ilość punktów widokowych w parku. Następnie danych jest n-1 linii, z których każda zawiera dwie liczby ai, bi (1 ≤ ai, bi ≤ n) oznaczające, że istnieje ścieżka między punktami widokowymi o numerach ai oraz bi.
Na wyjściu należy wypisać jedną liczbę - minimalną ilość szlaków wystarczającą do pokrycia wszystkich ścieżek w parku zgodnie z ograniczeniami podanymi w treści zadania.
Dla danych wejściowych
10
5 8
7 2
3 1
4 10
8 10
9 6
6 1
2 10
10 6
poprawną odpowiedzią jest
3
Przykładowe trzy szlaki pokrywające wszystkie ścieżki przechodzą przez punkty widokowe o numerach:
Odnośniki:
[1] http://www.cplusplus.com/reference/clibrary/cstdio/printf/
[2] http://www.cplusplus.com/reference/clibrary/cstdio/scanf/
[3] http://www.cplusplus.com/reference/iostream/cout/
[4] http://www.cplusplus.com/reference/iostream/cin/