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**?!".

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?".

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!
h2. Date de intrare

Fişierul de intrare $pang.in$ ...

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.

h2. Date de ieşire