== include(page="template/taskheader" task_id="freakadebunic") ==
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 conctracara cu arcasi in nodurile "devreme". Numim nod "devreme", primul nod comun din drumurile inspre nodul 1 a oricare doua grupe de ostasi.
Determinati in cate noduri "devreme" are Bunicu' de trimis arcasi.
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") ==
