Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sortop.in, sortop.out | Sursă | Algoritmiada 2016 Runda 3 Seniori |
| Autor | Adrian Budau, Eugenie Daniel Posdarascu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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 aibe o valoare mai mica decat fii 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.
- Radacina nu se stie care e.
Dandu-se arborele si cele K noduri fixate, determinati o sortare topologica valida a acestui arbore. Orice solutie este acceptata.
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. Al i-ulea numar reprezinta valoarea cu care a fost numerotat nodul i.
Restricţii
- 5 ≤ N ≤ 100.000
- 2 ≤ K ≤ N
Exemplu
| sortop.in | sortop.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
