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.

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.