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 căutarea sensului existenţei. Pe drum zăreşte ceva nemaivăzut şi îşi aduce aminte de replicile clasice din filme: "E o pasăre ...... E un avion ....... E ....... un graf?!".
Da, ai auzit bine, e un graf! Şi nu orice tip de graf, ci unul orientat aciclic. Mephisto, plictisit şi crezând că nu are ceva mai bun de făcut, ajunge la acest graf de pe planeta X şi vede lângă el şi un şir de indici distincţi. Imediat îi vine următoarea întrebare: "Dacă aş putea permuta cumva acest şir pot creea un drum începând de la primul nod, trecând prin toate nodurile din şir şi terminându-se la ultimul nod?". După ce hoinăreşte craterele de prin vecinătate, observă că această planetă este plină de grafuri şi şiruri de indici.
Nu stă prea mult pe gânduri şi-şi dă seama că spaţiul de posibilităţi este imens chiar şi pentru un semi-zeu. De aceea iţi cere ajutorul!
Date de intrare
Fişierul de intrare pang.in va conţine pe prima linie un număr T reprezentând numărul de teste la care trebuie să răspunzi. După vor urma T teste astfel: Pe prima linie se vor afla N, M şi K reprezentând numărul de noduri din graf, numărul de muchii din graf şi numărul de indici din şir. Pe următoarele M linii se afla 2 numere A şi B reprezentând faptul că există o muchie orientată de la A spre B. Pe ultima linie se va afla un şir de K numere, reprezentând indicii nodurilor din graf.
Date de ieşire
Fişierul de ieşire pang.out va conţine T linii de forma:
- " Nu " ( fară ghilimele ), în caz că nu există nicio permutare cu proprietatea din enunţ
- " Da " ( fară ghilimele ), în caz contrar. Pe cea de-a doua linie se va afla şirul permutat
Restricţii
- 1 ≤ K ≤ N ≤ 105
- 1 ≤ M ≤ 2*105
- Nodurile sunt numerotate de la 1 la N
Exemplu
| pang.in | pang.out |
|---|---|
| 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 |
