==Include(page="template/taskheader" task_id="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 care 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
 
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/taskheader" 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")==

1311