CT

ct

==Include(page="template/taskheader" task_id="ct")==

== include(page="template/taskheader" task_id="ct") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| ct.in | ct.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="ct") ==

==Include(page="template/raw")==
 
CT
 
 
 
Intr-o tara exista N orase, numerotate cu numere de la 1 la N. Orasele sunt conectate de strazi astfel incat exista un singur mod de a ajunge de la un oras la altu folosind strazile existente. In aceasta tara K organizatii teroriste fac planuri pentru distrugerea lumii, de aceea echipa CT s-a decis sa ii opreasca. Fiecare grupare terorista are cate o baza in doua din orasele tarii(deasemenea poate avea ambele baze in acelasi oras). Zilnic teroristii merg de la o baza la alta folosind strazile existente, ducand cu ei planurile pentru dominarea lumii. Bombardarea unui oras C va distruge acel oras si toate perechile de orase pentru care drumul dintre ele trecea prin orasul C vor ramane deconectate. Neutralizarea unei grupari teroriste consta in deconectarea oraselor care contin bazele gruparii respective sau in bombardarea a cel putin un oras care contine o baza a gruparii respective. Deoarece bombardarea oraselor implica si moartea unor civili neajutorati echipa CT doreste sa bombardeze cat mai putine
orase pentru a neutraliza toate cele K organizatii teroriste.
 
h2. Cerinta
 
Gasiti numarul minim de orase pe cae echipa CT trebuie sa le bombardeze.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare ct.in contine T, numarul de teste din fisier apoi vor urma cele T teste. Pe prima linie a fiecarui test se afla doua numere N si K numarul de orase respectiv numarul gruparilor teroriste. Urmeaza apoi N-1 linii continand cate doua numere x, y cu semnificatia exista strada intre orasele x si y. In continuare vor fi K linii, pe linia i aflandu-se doua numere ce reprezinta orasele in care se afla sediul organizatiei i.
 
h2. Date de Iesire
 
In fisierul ct.out vor exista T linii fiecare continand numarul minim de orase ce trebuie bombardate pentru tara respectiva.
 
h2. Restrictii si precizari
 
. 1 <= N <= 100.000
 
. 1 <= K <= 100.000
 
. 1 <= T <= 5
 
h2. Exemplu
 
 
|ct.in |ct.out |
 
|1 |2 |
|11 5 | |
|1 2 | |
|2 3 | |
|3 4 | |
|2 5 | |
|5 6 | |
|5 11 | |
|7 1 | |
|10 7 | |
|8 7 | |
|9 8 | |
|4 6 | |
|3 11 | |
|5 9 | |
|10 9 | |
|8 2 | |
 
 
 
 
Explicatii
 
Se pot bombarda orasele 2 si 7 neutralizand astfel toate gruparile teroriste.
==Include(page="template/taskfooter" task_id="ct")==