== include(page="template/taskheader" task_id="freakadebunic") ==
Poveste şi cerinţă...
Traind vremuri grele in care 'frica de Bunic' este la ordinul zilei, Paula din tinutul Fleschinului se hotaraste sa ia atitudine si sa-l detroneze pe marele Bunic. Taramul Freschinului poate fi reprezentat ca un arbore cu muchii bidirectionale, format din N noduri, iar in nodul 1 avand sediu Bunicu'. Paula pregateste de asalt trupe, pozitionandu-le in K noduri diferite. Bunicu', de asemenea, va contracara cu arcasi in nodurile "devreme". Numim nod "devreme", primul nod comun din drumurile inspre nodul 1 a oricaror doua trupe.
Determinati in cate noduri "devreme" are Bunicu' de trimis arcasi, dar si care sunt acestea.
h2. Date de intrare
Fişierul de intrare $freakadebunic.in$ ...
Fişierul de intrare $freakadebunic.in$ va contine pe prima linie 2 numere: N (numarul de noduri) si K (numarul de noduri cu trupe). Pe a doua linie se vor afla K numere diferite reprezentand nodurile unde va trimite Paula trupe. Pe urmatoarele N-1 linii, se vor afla cate 2 numere A si B, reprezentand ca exista muchie intre nodurile A si B.
h2. Date de ieşire
În fişierul de ieşire $freakadebunic.out$ ...
În fişierul de ieşire $freakadebunic.out$ contine pe prima linie un singur numar T reprezentand numarul de noduri "devreme", iar pe a 2-a linie T numere ordonate crescator reprezentand nodurile "devreme".
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ K ≤ N ≤ 100.000$
* Pentru 30 de puncte, $1 ≤ K ≤ N ≤ 1000$
* Pentru alte 30 de puncte, $1 ≤ K ≤ N ≤ 3000$
h2. Exemplu
table(example). |_. freakadebunic.in |_. freakadebunic.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 10 4
4 5 6 8
1 2
1 4
1 3
2 5
2 6
2 7
3 8
3 9
6 10
| 2
1 2 |
| 7 4
4 5 6 7
1 2
1 3
1 4
3 5
4 6
6 7
| 3
1 4 6 |
h3. Explicaţie
...
In primul exemplu, drumul trupelor din nodul 5 inspre 1 este: 5-> 2-> 1, iar drumul trupelor din nodul 6 inspre 1 este: 6-> 2-> 1. Primul nod comun al acestor drumuri inspre nodul 1 este nodul 2. Daca in nodul 10 erau trupe ale Paulei, drumul inspre nodul 1 era: 10-> 6-> 2-> 1. Primul nod comun din drumurile trupelor din nodurile 5 si 10 este, de asemenea, nodul 2. In ambele cazuri, nodul 2 este nod "devreme".
== include(page="template/taskfooter" task_id="freakadebunic") ==
