Gaśnice

Limit pamięci: 64 MB

Bajtazar zbudował nowy pałac. Pałac ten składa się z pokoi i łączących je korytarzy. Pokoje są ponumerowane od do . Do pałacu jest jedno wejście, prowadzące do pokoju nr . Każdy korytarz łączy dwa różne pokoje. Do każdego pokoju prowadzi od wejścia dokładnie jedna droga (bez zawracania). Inaczej mówiąc, pokoje i łączące je korytarze tworzą drzewo - spójny graf acykliczny.

Inspektor straży pożarnej, który odbierał pałac, domaga się umieszczenia w pałacu gaśnic. Określił on następujące wymagania:

  • Gaśnice mają być umieszczone w niektórych pokojach, przy czym w jednym pokoju może znaleźć się kilka gaśnic.
  • Każdemu pokojowi trzeba przydzielić jedną konkretną gaśnicę.
  • Każda z gaśnic może być przydzielona do gaszenia co najwyżej różnych pokoi.
  • Dotarcie z dowolnego pokoju do przypisanej mu gaśnicy może wymagać przejścia co najwyżej korytarzy.
Bajtazar, jak to zwykle bywa po zakończeniu budowy, ma bardzo mało pieniędzy. Zastanawia się więc, jaka minimalna liczba gaśnic wystarczy do spełnienia powyższych wymagań?

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , i pooddzielane pojedynczymi odstępami, , , . Każdy z następnych wierszy zawiera po dwie liczby całkowite oddzielone pojedynczym odstępem. W wierszu znajdują się liczby reprezentujące korytarz łączący pokoje nr i .

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia powinna zostać wypisana jedna liczba całkowita - minimalna liczba gaśnic, jakie należy zainstalować w pałacu.

Przykład

Dla danych wejściowych:

12 3 1
1 12
3 8
7 8
8 9
2 12
10 12
9 12
4 8
5 8
8 11
6 8

poprawną odpowiedzią jest:

4

Autor zadania: Paweł Parys.