Zadanie

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

Sada 1 2 3 4 5 6 7 8 9 10
\(n \leq\) 1000 1000 1000 10000 10000 100000 100000 100000 100000 100000
\(m \leq\) 2000 20000 500000 50000 50000 300000 300000 300000 300000 300000
\(q =\) \(n\) \(n\) \(n\) \(n\) \(n\) 1 1 \(n\) \(n\) \(n\)

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

Ak sa hrana \(a, b\) nachádza na vstupe (teda \(a\) a \(b\) nie sú spojené hranou), budeme hovoriť, že \(a\) je antisused \(b\) a tiež \(b\) je antisused \(a\).

Jednoduché riešenie v čase \(O(n^2)\): prehľadávame do šírky. Vždy, keď chceme nájsť susedov niektorého vrchola \(v\), urobíme si pole \(susedia\) dĺžky \(n\), v ktorom na začiatku zaznačíme, že každý vrchol ešte môže byť susedom \(v\). Následne prechádzame zoznam antisusedov \(v\). Ak \(b\) je antisused \(v\), do poľa susedia si zaznačíme, že \(b\) nie je susedom \(v\).

Na konci tohto procesu vieme z poľa \(susedia\) zostrojiť zoznam susedov \(v\). To je jediné, čo potrebujeme pri prehľadávaní do šírky.

Jediné, čo nás delí od rýchleho riešenia, je nasledovné pozorovanie: Označme \(visited\) množinu vrcholov, ktoré sme doposiaľ v našom prehľadávaní navštívili. Potom nepotrebujeme pre žiaden z vrcholov vo \(visited\) vedieť, či susedí s \(v\) alebo nie – aj keby susedil, prehľadávanie v ňom nebude pokračovať, lebo ten vrchol bol navštívený už predtým.

Spracovanie vrcholu \(v\) bude teda prebiehať nasledovne – nech \(notvisited\) je štruktúra, ktorá obsahuje prehľadávaním dosiaľ nenavštívené vrcholy. Prejdeme zoznamom antisusedov \(v\). Ak \(b\) je antisused \(v\) a zároveň \(b\) je v \(notvisited\), tak si zaznačíme, že \(b\) stále nebude navštívené – vrchol \(b\) označíme. Na záver prejdeme zoznamom všetkých vrcholov v \(notvisited\), a každý vrchol, ktorý sme neoznačili, pridáme do fronty a vyhodíme z \(notvisited\).

Čitateľovi prenechávame na rozmyslenie, ako možno implementovať štruktúru \(notvisited\) a aká je časová zložitosť výsledného algoritmu.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.