Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pang.in, pang.out | Sursă | FMI No Stress 2017 |
| Autor | Baltatu Andrei | Adăugată de |  Fmi No Stress 7 •fmins7 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pang Bang
Mephisto, plictisit de Faust şi toate dorinţele lui, pleacă pe alte tărâmuri în cautarea sensului existenţei. 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?!".
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.
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!
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.
Date de ieşire
Fisierul de iesire pang.out va contine T linii de forma:
- " 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
Restricţii
- 1 ≤ K ≤ N ≤ 105
- 1 ≤ M ≤ 2*105
- Nodurile sunt numerotate de la 1 la N
- Un drum simplu reprezinta un drum in care nu se repeta nodurile sau muchiile
Exemplu
| pang.in | pang.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
