Runda 2: Górskie szlaki

24.06.2009

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

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).
Uwaga: Ze względu na duży rozmiar danych zaleca się obsługiwanie standardowego wejścia i wyjścia za pomocą funkcji printf(...) i scanf(...) zamiast strumieni cout i cin.
kod: MOUNTPATH, limity: 4 s, 32 MB

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com