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