sortop

Sortop

== include(page="template/taskheader" task_id="sortop") ==

Poveste şi cerinţă...

Se da un arbore cu $N$ noduri. O sortare topologica a acestui arbore constituie o numerotare a celor $N$ noduri cu valori distincte de la $1$ la $N$, astfel incat fiecare parinte in arbore sa aibă o valoare mai mica decat fiii lui (nodul $1$ este radacina, nodul $N$ este mereu frunza).
 
Sarcina voastra este sa gasiti o sortare topologica valida pentru acest arbore. Aveti in schimb $2$ detalii ce trebuie sa luati in considerare:
 
* $K$ din cele $N$ noduri au valoarea fixata (ordinea in sortarea topologica este prestabilita). Sarcina ramane sa completati celalalte $N - K$ noduri.
* Valoarea rădăcinii nu este neaparat fixată.
 
Dandu-se arborele si cele $K$ noduri fixate, determinati o sortare topologica valida a acestui arbore. Orice solutie este acceptata. Dacă nu există soluţie, se va afişa $-1$.

h2. Date de intrare

Fişierul de intrare $sortop.in$ ...

Fişierul de intrare $sortop.in$ va contine pe prima linie $2$ numere naturale $N$ si $K$. Pe urmatoarele $N - 1$ linii se vor afla cate $2$ numere naturale $X$ si $Y$ reprezentand faptul ca aveti muchie de la $X$ la $Y$. Urmatoarele $K$ linii contin cate alte $2$ numere naturale $X$ si $Y$ reprezentand faptul ca nodul $X$ a fost numerotat cu valoarea $Y$.

h2. Date de ieşire

În fişierul de ieşire $sortop.out$ ...

Fişierul de ieşire $sortop.out$ va contine pe o singura linie $N$ numere naturale reprezentand sortarea topologica a arborelui din datele de intrare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $5 ≤ N ≤ 100.000$
* $2 ≤ K ≤ N$
* Pentru teste in valoare de 50 de puncte $N ≤ 1000$.

h2. Exemplu
table(example). |_. sortop.in |_. sortop.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 8 3
  1 2
  1 3
  3 4
  4 5
  1 6
  6 7
  7 8
  1 2
  5 4
  8 7
| 3 1 4 5 6 7 8 2

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="sortop") ==