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 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 un 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
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 |
