Łuk triumfalny

Limit pamięci: 128 MB

Król Bajtocji, Bajtazar, wraca po zwycięskiej bitwie do swojego kraju. W Bajtocji jest miast połączonych zaledwie drogami. Wiadomo, że z każdego miasta da się dojechać do każdego innego dokładnie jedną trasą, złożoną z jednej lub większej liczby dróg. (Inaczej mówiąc, sieć dróg tworzy drzewo).

Król właśnie wkroczył do stolicy Bajtocji. W mieście tym postawiono łuk triumfalny, czyli bramę, pod którą przejeżdża król po odniesieniu zwycięstwa. Bajtazar, zachwycony przyjęciem przez poddanych, zaplanował pochód triumfalny, w którym odwiedzi wszystkie miasta Bajtocji, zaczynając z miasta, w którym aktualnie przebywa.

Pozostałe miasta nie są przygotowane na przyjazd króla - nie zostały w nich jeszcze postawione łuki triumfalne. Nad budową łuków czuwa doradca Bajtazara. Chce on zatrudnić pewną liczbę ekip budowlanych. Każda ekipa codziennie może wybudować jeden łuk, w dowolnie wybranym mieście. Niestety nikt nie wie, w jakiej kolejności król będzie odwiedzał miasta. Wiadomo jedynie, że każdego dnia król przemieści się z miasta, w którym się aktualnie znajduje, do sąsiedniego miasta. Król może odwiedzać poszczególne miasta dowolnie wiele razy (jednak wystarczy mu jeden łuk triumfalny w każdym mieście).

Doradca Bajtazara musi zapłacić każdej ekipie budowlanej tyle samo, bez względu na to, ile zbuduje łuków triumfalnych. Z jednej strony, doradca chce mieć pewność, że każde miasto aktualnie odwiedzane przez króla będzie miało łuk triumfalny. Z drugiej jednak strony chciałby zatrudnić jak najmniej ekip budowlanych. Pomóż mu i napisz program, który pomoże wyznaczyć minimalną konieczną liczbę ekip budowlanych.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę miast w Bajtocji. Miasta są ponumerowane od 1 do , przy czym stolica Bajtocji ma numer 1.

Sieć dróg Bajtocji jest opisana w kolejnych wierszach. Każdy z tych wierszy zawiera dwie liczby całkowite () oddzielone pojedynczym odstępem, oznaczające, że miasta i są połączone bezpośrednio dwukierunkową drogą.

W testach wartych łącznie 50% punktów zachodzi dodatkowy warunek .

Wyjście

Pierwszy i zarazem jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnej liczbie ekip budowlanych, które powinien zatrudnić doradca Bajtazara.

Przykład

Dla danych wejściowych:

7
1 2
1 3
2 5
2 6
7 2
4 1

poprawną odpowiedzią jest:

3

Wyjaśnienie do przykładu: W pierwszym dniu należy wybudować łuki triumfalne w miastach 2, 3, 4. Później wystarczy je zbudować w miastach 5, 6, 7.

Testy "ocen":

• 1ocen: , miasta tworzą pełne drzewo binarne o wysokości 12;
• 2ocen: , miasta są ułożone wzdłuż jednej ścieżki;
• 3ocen: , prosty test poprawnościowy;
• 4ocen: , prosty test poprawnościowy;
• 5ocen: , dziewięć długich ścieżek zwisających z korzenia.

Autor zadania: Jacek Tomasiewicz.