1. Tajná základňa vzorové riešenie

Najčastejšie dve aktivity v “Krčme u starého psa” sú bitie a pitie. Dokonca aj na pomery spoločensky unavených ľudí sa bitky odohrávajú príliš často. Nie je to náhoda – krčma je totiž súčasťou tajnej vojenskej základne a bitkári sú v skutočnosti veteráni trénujúci drunken-style.

Základňa pozostáva z viacerých miestností a medzi každou dvojicou miestností vedie práve jedna chodba. Za účelom čo najintenzívnejšieho tréningu sú niektoré chodby vybavené lávovými gejzírmi, padajúcimi stropmi, pichliačmi, kyvadlami, …

Občas na základňu prídu významné osobnosti, ako napríklad pán prezident či najvyšší generál. Pán prezident by sa rád dostal do centrály a generál by chcel vidieť svojho syna. Nemajú však celý deň a chceli by sa dostať na miesto určenia čo najrýchlejšie.

Bežný vojak by sa do cieľa dostal priamo cez chodbu s rotujúcimi čepeľami a chodbou s rozpadajúcou sa podlahou pokrytou klzkým ľadom. Väčšina návštevníkov ale na takéto nebezpečné cesty nemá potrebné skúsenosti. Našťastie, niektoré chodby neskrývajú žiadne nástrahy a sú bezpečné.

Vedenie základne vás požiadalo, aby ste naprogramovali navigačný systém pre návštevníkov. Systém, ktorý nájde pre daný cieľ najkratšiu bezpečnú cestu – cestu bez nástrah.

Úloha

Zadaný máte graf, ale nie štandardným spôsobom. Namiesto toho, aby ste dostali zoznam hrán, ktoré v grafe sú, dostanete zoznam hrán, ktoré v ňom nie sú (zoznam nebezpečných chodieb).

Všetky hrany (medzi dvoma rôznymi vrcholmi), ktoré nedostanete na vstupe, v grafe sú.

Tiež dostanete zadaný vrchol vstupnej haly.

Na záver dostanete zadaných niekoľko cieľových vrcholov. Pre každý nájdite najkratšiu cestu v grafe vedúcu zo vstupnej haly do daného vrchola. Dĺžka cesty je počet hrán na nej. Ak je najkratších ciest viac, vypíšte ľubovoľnú.

Formát vstupu

Na prvom riadku vstupu sú tri celé čísla \(n, m, s\) – počet vrcholov, počet hrán, ktoré nie sú v grafe, a číslo vrchola vstupnej haly. Platí \(n \leq 10^5,~ m \leq 5 \cdot 10^5,~ 0 \leq s < n\).

Na každom z nasledujúcich \(m\) riadkov sú dve čísla \(0 \leq a, b < n\), hovoriace o neexistencii hrán medzi vrcholmi \(a\) a \(b\) v oboch smeroch. Každá dvojica sa na vstupe vyskytne najviac raz a \(a \neq b\).

Na ďalšom riadku je číslo \(q\), udávajúce počet cieľových vrcholov. Na každom z nasledujúcich \(q\) riadkov je jedno celé číslo \(0 \leq c < n\) – číslo cieľového vrchola. Je zaručené, že žiadne dva cieľové vrcholy nie sú rovnaké.

Formát výstupu

Pre každý cieľový vrchol vypíšte na samostatný riadok cestu vedúcu zo vstupnej haly doň v nasledujúcom formáte: \(d\ v_1\ v_2\ \ldots\ v_d\), kde \(d\) je dĺžka cesty (počet chodieb na ceste), \(s\) je prvý navštívený vrchol, \(v_1\) je nasledujúci navštívený, …, \(v_d\) je posledný navštívený vrchol (zhodný s cieľovým vrcholom). Ak cesta neexistuje, vypíšte namiesto toho \(-1\).

Obmedzenia na vstupy

Príklad

Input:

5 6 0
0 2
0 3
0 4
1 3
1 4
2 4
5
0
1
2
3
4

Output:

0
1 1
2 1 2
3 1 2 3
4 1 2 3 4

Input:

7 9 6
0 2
0 3
0 4
0 5
0 6
1 3
1 4
1 5
1 6
7
0
1
2
3
4
5
6

Output:

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