== include(page="template/taskheader" task_id="cezar") ==

== include(page="template/autor-necunoscut") ==
 

In Roma antica exista {$N$} asezari senatoriale distincte, cate una pentru fiecare dintre cei $N$ senatori ai Republicii. Asezarile senatoriale sunt numerotate de la $1$ la $N$, intre oricare doua asezari existand legaturi directe sau indirecte. O legatura este directa daca ea nu mai trece prin alte asezari senatoriale intermediare. Edilii au pavat unele dintre legaturile directe dintre doua asezari (numind o astfel de legatura pavata "strada"), astfel incat intre oricare doua asezari senatoriale sa existe o singura succesiune de strazi prin care se poate ajunge de la o asezare senatoriala la cealalta.
Toti senatorii trebuie sa participe la sedintele Senatului. In acest scop, ei se deplaseaza cu lectica. Orice senator care se deplaseaza pe o strada plateste $1$ ban pentru ca a fost transportat cu lectica pe acea strada.
La alegerea sa ca prim consul, Cezar a promis ca va dota Roma cu o lectica gratuita care sa circule pe un numar de $K$ strazi ale Romei astfel incat orice senator care va circula pe strazile respective, sa poata folosi lectica gratuita fara a plati. Strazile pe care se deplaseaza lectica gratuita trebuie sa fie legate intre ele (zborul, metroul sau teleportarea nefiind posibile la acea vreme).

h2. Restrictii

* $1$ < $N$ &le; $10000$
* $0$ < $K$ < $N$
* $1$ &le; $i$ , $j$ &le; $N$ , $i$ &ne; $j$

* {$1 < N &le; 10000$}
* {$0 < K < N$}
* {$1 &le; i, j &le; N, i &ne; j$}

* Oricare doua perechi de valori de pe liniile $2$, $3$,..., $N$ din fisierul de intrare reprezinta doua strazi distincte.
* Perechile din fisierul de intrare sunt date astfel incat respecta conditiile din problema.

* Pentru $25%$ din teste $N$ &le; $30$, pentru $25%$ din teste $30$ < $N$ &le; $1000$, pentru $30%$ din teste $1000$ < N &le; $3000$, pentru $10%$ din teste $3000$ < $N$ &le; $5000$,  pentru $10%$ din teste $5000$ < $N$ &le; $10000$.

* Pentru $25%$ din teste {$N &le; 30$}, pentru $25%$ din teste {$30 < N &le; 1000$}, pentru $30%$ din teste {$1000 < N &le; 3000$}, pentru $10%$ din teste {$3000 < N &le; 5000$},  pentru $10%$ din teste {$5000 < N &le; 10000$}.

h2. Exemplu

== include(page="template/taskfooter" task_id="cezar") ==

==SmfTopic(topic_id="...")==

2059