== include(page="template/taskheader" task_id="pang") ==
$Mephisto$, plictisit de Faust şi toate dorinţele lui, pleacă pe alte tărâmuri în cautarea sensului existenţei prin univers. Pe drum zăreşte ceva nemaivăzut şi îşi aduce aminte de replicile clasice din filme: "E o pasare ...... E un avion .... E ....... **un graf**?!".
h3. _De ce am numit-o aşa?_
Da, ai auzit bine, e un graf! Si nu orice tip de graf, ci unul **orientat aciclic**. Mephisto, plictisit si crezand ca nu are ceva mai bun de facut, ajunge la acest graf de pe planeta X si vede langa el si un **sir de indici distincti**. Imediat ii vine urmatoarea intrebare: "Daca as putea **permuta** cumva acest sir pot creea un **drum simplu** de la primul indice la ultimul?". Dupa ce hoinareste craterele de prin vecinatate, observa ca planeta aceasta este plina de grafuri si siruri de indici.
_Cu toţii ne dorim să trăim veşnic_. Din păcate însă, acest lucru este improbabil. Cu toate acestea, prietenul nostru Faust, filosof şi mare înţelept, are ocazia unică de a aplica pentru firma **Ludai România** unde _totul este posibil_. Desigur, însă, înainte de asta, va trebui să treacă prin nenumărate interviuri istovitoare (ţinute, cum bine aţi intuit, de către cunoscutul **Mefisto**).
Nu sta prea mult pe ganduri si-si da seama ca spatiul de posibilitati este imens chiar si pentru un semi-zeu. De aceea iti cere ajutorul!
Faust a fost anunţat că va trebui să ia parte în următoarele zile la $T$ probe existenţiale (de interviu). Din fericire pentru acesta, s-a produs o breşă în sistemul de poştă electronică (vinovatul nu a fost găsit), în aşa fel încât Faust, într-un mod foarte convenabil, a obţinut dinainte probele pentru toate cele $T$ zile. În mod foarte curios, toate zilele conţineau probe foarte asemănătoare. Faust a observat că enunţul problemei era identic în fiecare dintre zile:
_Eşti într-un tărâm necunoscut, care are $N$ oraşe. Unele oraşe sunt sărace, altele sunt bogate, însă $K$ dintre ele conţin relicve valoroase. Ce va trebui să faci este să "restitui" toate relicvele, în numele **Ludai România**. Poţi să porneşti din orice oraş doreşti şi poţi să te opreşti în orice oraş doreşti, însă o dată ce vei intra într-un oraş, **fii sigur că nu vei mai putea ajunge vreodată înapoi (în viaţă)**. Alege-ţi calea în mod înţelept!_
Alături de fiecare dintre cele $T$ enunţuri pe care Mefisto se pare că nu s-a obosit să le facă să pară câtuşi de puţin diferite, se află ataşată câte o descriere a tărâmului, relicvelor şi drumurilor directe între oraşe, într-un format identic cu cel din fişierul $pang.in$. Pentru simplitate, relicvele sunt identificate de oraşul în care se află.
Cum Faust nu e tocmai un neiniţiat la şiretlicurile lui Mefisto, acesta observă că, în unele dintre teste, călătoria este una imposibilă! Cu toate acestea, datele sunt atât de imense, încât este foarte rapid copleşit de dificultatea probei. Ajută-l pe Faust să treacă toate probele de interviu, scriind câte o "foaie ajutătoare" pentru acesta! Mai exact, pentru fiecare dintre cele $T$ probe, lui Faust i-ar plăcea să ştie dacă cerinţa din ziua respectivă este una posibilă şi, în caz afirmativ, să ştie în ce ordine să pornească în căutarea relicvelor. Astfel va putea, în sfârşit, să îşi retrăiască tinereţea (căci meseria de filosof nu i-a adus prea multe beneficii până acum).
h2. Date de intrare
Fisierul de intrare $pang.in$ va contine pe prima linie $1$ numar $T$ reprezentand numarul de teste la care trebuie sa raspunzi. Dupa vor urma $T$ teste astfel: Pe prima linia se va afla $N$, $M$ si $K$ reprezentand numarul de noduri din graf, numarul de muchii din graf si numar de indici din sir. Pe urmatoarele $M$ linii se afla $2$ numere $A$ si $B$ reprezentand faptul ca exista o muchie orientata de la $A$ spre $B$. Pe ultima linie se va afla un sir de $K$ numere, reprezentand indicii nodurilor din graf.
Fişierul de intrare $pang.in$ va conţine pe prima linie un număr $T$ reprezentând numărul de probe de interviu la care Faust va lua parte. După vor urma $T$ grupe astfel: Pe prima linie se vor afla $N$, $M$ şi $K$ reprezentând numărul de oraşe din tărâm, numărul de căi de acces şi numărul de relicve. Pe următoarele $M$ linii se afla $2$ numere $A$ şi $B$ reprezentând faptul că se poate ajunge în mod direct din oraşul $A$ spre oraşul $B$ (acest lucru nu implică faptul că se poate ajunge şi din $B$ în $A$). Pe ultima linie se va afla un şir de $K$ numere, reprezentând indicii oraşelor în care se află cele $K$ relicve.
h2. Date de ieşire
Fisierul de iesire $pang.out$ va contine $T$ linii de forma:
Fişierul de ieşire $pang.out$ va conţine, pentru fiecare dintre cele $T$ probe:
* " **Nu** " ( _fara ghilimele_ ), in caz ca nu exista nicio permutare cu proprietatea din enunt
* " **Da** " ( _fara ghilimele_ ), in caz contrar. Pe cea de-a doua linie se va afla sirul permutat
* Cuvântul " $Nu$ " ( _fară ghilimele_ ), în caz că nu există modalitate de a "restitui" cele $K$ relicve, pe o singură linie
* Cuvântul " $Da$ " ( _fară ghilimele_ ), în caz contrar, pe prima linie. Pe cea de-a doua linie se va afla şirul oraşelor în care se află relicvele, în ordinea în care vor fi recuperate.
h2. Restricţii
* $1 ≤ K ≤ N ≤ 100000$
* $1 ≤ K ≤ N ≤ 10^5^$
* $1 ≤ M ≤ 2*10^5^$
* Oraşele sunt numerotate de la $1$ la $N$
* Suma tuturor $N$-urilor din input nu va depăşi $10^5^$
* Suma tuturor $M$-urilor din input nu va depăşi $2*10^5^$
* Se garantează faptul că, o dată plecat dintr-un oraş $A$, Faust nu va mai avea nicio modalitate prin care să se poată întoarce în oraşul $A$.
h2. Exemplu
table(example). |_. pang.in |_. pang.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
4 4 3
1 2
1 3
2 3
3 4
2 4 1
3 2 3
1 2
1 3
3 1 2
| Da
1 2 4
Nu
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="pang") ==
