Runda 2: Górskie szlaki

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!

Wejście

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 a_i, b_i (1 ≤ a_i, b_i ≤ n) oznaczające, że istnieje ścieżka między punktami widokowymi o numerach a_i oraz b_i.

Wyjście

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.

Przykład

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:

• 3,1,6,10,8,5 (szlak czerwony);
• 9,6,10,4 (szlak niebieski);
• 7,2,10,4 (szlak zielony).