Rímska ríša je známa svojimi cestnými sieťami. Ale aby si mohli zachovať slávu, treba ich samozrejme pravidelne opravovať. A kto iný by ich opravoval, keby nie plebejci? Existuje $p$ tímov plebejcov, rozmiestnených po rôznych mestách ríše, pričom treba, aby o $k$ dní išli opravovať cesty v nejakých iných $p$ mestách ríše. Samozrejme, ako Patricij stojaci v čele Koordinácie Siete Plebejcov nemôžeš dovoliť, by sa proti tebe plebejci spolčili. Preto by nikdy nemali dva opravárske tímy ostávať v jednom meste.

Tímy vedia putovať iba po cestách, pričom prechod jednou cestou trvá deň, alebo môžu zostávať v meste v ktorom sú. Zistite, či sa po $k$ dňoch vedia prepraviť tam, kam treba.

Úloha

Rímsku cestnú sieť tvorí $n$ miest ktoré spája $m$ ciest. Cesty sa nekrižujú, sú obojsmerné a medzi mestami sa dá dostať iba po cestách, pričom prejsť každú cestu trvá jeden deň.

V $p$ rôznych mestách $a_1, \dots, a_p$ je rozmiestnených $p$ opravárskych tímov. Potrebujeme, aby po $k$ dňoch tímy pôsobili v mestách $b_1,\dots,b_p$, pričom nám nezáleží na tom, ktorý tím skončí v ktorom meste.

Tímy sa vedia presúvať nasledovne: každý deň sa tím buď presunie jednou cestou do susedného mesta, alebo ostane na mieste. Na konci žiadneho dňa nemôžu dva rôzne tímy skončiť v jednom meste (môžu však okolo seba prejsť po ceste).

Zistite, či po $k$ dňoch vedia tímy skončiť v mestách $b_1, \dots, b_p$ a ak áno, ako.

Formát vstupu

V prvom riadku vstupu sú štyri čísla oddelené medzerou: $1\leq n, m, p, k$. Vo všetkých vstupoch platí $p\leq n \leq 1\,000$, $m\leq \max(1\,000, \frac{n(n-1)}{2})$ a $k\leq 50$.

Na druhom riadku vstupu sa nachádza $p$ medzerou oddelených čísel: $a_1,a_2, \dots, a_p$ - pôvodné rozmiestnenie tímov. Je garantované, že sú všetky navzájom rôzne.

Na treťom riadku vstupu sa nachádza $p$ medzerou oddelených čísel: $b_1,b_2 \dots, b_p$ - požadované rozmietnenie tímov. Je garantované, že sú všetky navzájom rôzne.

Na ďalších $m$ riadkoch sa nachádza popis ciest. Popis cesty pozostáva z dvoch medzerou oddelených čísel miest, ktoré cesta spája. Je garantované, že každá cesta spája dve rôzne mestá, a žiadnu dvojicu miest nespájajú dve rôzne cesty.

Mestá číslujeme od $1$ po $n$.

Existujú $4$ testovacie sady. V nich navyše existujú nasledujúce obmedzenia:

• V prvej sade platí, že cesty môžu viesť iba medzi mestami $i$ a $i + 1$ (nie všetky takéto cesty však musia existovať).
• V druhej sade platí $p = 1$
• V tretej sade platí $k = 1$.

Formát výstupu

Na prvom riadku vypíšte buď ANO (ak je možné po $k$ dňoch dostať tímy na požadované miesta) alebo NIE (ak to možné nie je).

V prípade, že vypíšete ANO, vypíšte ďalších $p$ riadkov, každý z nich obsahujúci $k$ čísel oddelených medzerou. Na $i$-tom riadku vypíšte pohyb tímu, ktorý začínal v meste $a_i$. Formálne teda $k$ čísel, $j$-te z nich reprezentuje mesto, v ktorom sa $i$-ty tím nachádzal po $j$-tom dni.

Príklady

5 5 2 1
1 3
2 5
1 5
1 3
1 4
3 4
2 3

ANO
5
2

Všimnime si, že tím ktorý začínal na pozícii $a_1 = 1$ skončí na pozícii $b_2 = 5$. Tento vstup by sa mohol objaviť v tretej sade.

5 5 2 2
3 4
5 2
1 2
1 3
1 4
1 5
3 4

NIE

Aby sa tímy dostali na koncové pozície, potrebovali by sa oba po prvom dni nachádzať v vrchole číslo $1$. Keďže to ale nemôžu odpoveď je NIE.

Ak by však mali na presun $3$ dni, išlo by to napríklad tak, že by prvý tím prvý deň ostal na mieste.

10 10 4 2
2 5 6 7
5 4 10 2
1 2
2 3
3 1
4 5
5 6
6 7
7 8
8 9
9 10
10 4

ANO
2 2
4 10
5 4
6 5

Jedno z možných riešení. Všimnite si, že cestná sieť nemusí byť spojitá.