Fişierul intrare/ieşire:sortop.in, sortop.outSursăAlgoritmiada 2016 Runda 3 Seniori
AutorAdrian Budau, Eugenie Daniel PosdarascuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sortop

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.

Date de intrare

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.

Date de ieşire

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.

Restricţii

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

Exemplu

sortop.insortop.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?