ct

CT

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

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

Poveste ...

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 care echipa CT trebuie sa le bombardeze.

h2. Restrictii

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 intrare

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. Date de iesire

h2. Restrictii si precizari

...

* $1 ≤ N ≤ 100.000$
* $1 ≤ K ≤ 100.000$
* $1 ≤ T ≤ 5$

h2. Exemplu

| ct.in | ct.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. ct.in |_. ct.out |
|1
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 | 2 |
 
h3. Explicatii
 
Se pot bombarda orasele 2 si 7 neutralizand astfel toate gruparile teroriste.
 
==Include(page="template/taskfooter" task_id="ct")==
 

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

1311