Mai intai trebuie sa te autentifici.
Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2017-03-08 20:27:16.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:pang.in, pang.outSursăFMI No Stress 2017
AutorBaltatu AndreiAdăugată defmins7Fmi No Stress 7 •fmins7
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inpang.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?