Fişierul intrare/ieşire:ct.in, ct.outSursăHappy Coding 2006
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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 care 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.inct.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content