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.