Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | ct.in, ct.out | Sursă | Happy Coding 2006 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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.
Cerinta
Gasiti numarul minim de orase pe cae echipa CT trebuie sa le bombardeze.
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.
Date de Iesire
In fisierul ct.out vor exista T linii fiecare continand numarul minim de orase ce trebuie bombardate pentru tara respectiva.
Restrictii si precizari
- 1 ≤ N ≤ 100.000
- 1 ≤ K ≤ 100.000
- 1 ≤ T ≤ 5
Exemplu
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 |
Explicatii
Se pot bombarda orasele 2 si 7 neutralizand astfel toate gruparile teroriste.