Ł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.