4. Koľko strihaní potrebujeme?

Pokojne sedíte vo svojej kancelárii a vychutnávate si kávu. Ste radi, že vás práve povýšili na CEO celoštátnej firmy „Kolosálne Spojenie Psikov“ a užívate si výhľad zo svojho okna. Spomínate si, ako ste začínali pracovať pre túto firmu, ktorá rozdeľuje elektrinu do všetkých miest nášho milovaného štátu. Pamätáte si výstavbu masívnej elektrárne a pokladanie káblov medzi našimi malebnými mestami.

Zrazu začujete krik a do vašej kancelárie vbehne vaša sekretárka Miška s desivou správou: gigantická elektráreň má problémy a jej produkcia elektriny kolíše. To môže viesť k preťaženiu siete a následným explóziám rozvodných staníc. Vypnúť elektráreň nie je možné, pretože by to zruinovalo vašu firmu. Našťastie vás napadne riešenie:

Každé mesto má rozvodnú stanicu, ktorú viete na diaľku vypnúť. Tým odpojíte mesto od siete, čím riskujete kritiku. Aby ste predišli kolapsu, potrebujete vypínať mestá v takom poradí, že ak odpojíte od siete prvých \(j\) miest v poradí, všetky zvyšné mesta zostanú spojené s elektrárňou.

Úloha

Elektrická sieť pozostáva z \(n\) miest, očíslovaných od \(0\) po \(n-1\), \(m\) káblov a práve jednej elektrárne, ktorá sa nachádza v meste \(k\). Elektrina prúdi od elektrárne do všetkých miest, do ktorých sa z nej dá dostať káblom (káble vedia prenášať energiu obojsmerne).

Keď vypneme mesto od elektriny, vypneme všetky káble ktoré cez neho vedú, a teda cez neho nesmie ani prúdiť elektrina do iných miest.

Nájdite postupnosť v ktorej vieme odpájať mestá od elektriny, tak aby pre každé \(1 \leq j \leq n\) platilo, že ak od elektriny odpojíme prvých \(j\) miest, neovplyvníme tak elektrinu do zvyšných \(n-j\) miest.

Všimnite si, že ak od elektriny odpojíte mesto s elektrárňou, do ďalších miest už elektrina ísť nevie (nemá odkiaľ).

Formát vstupu

• Prvý riadok obsahuje čísla \(1 \leq n \leq 10^5\) (počet miest), \(0\leq m \leq \min(2\cdot 10^5, \frac{n(n-1)}{2})\) (počet káblov) a \(0\leq k\leq n - 1\) (číslo mesta s elektrárňou), oddelené medzerou.
• Nasleduje \(m\) riadkov s dvojicami čísel \(0\leq a_i\neq b_i\leq n-1\) oddelených medzerou, označujúcich, že medzi mestami \(a_i\) a \(b_i\) sa nachádza kábel.

Je garantované, že v zadanej elektrickej sieti má každé mesto prístup k elektrine.

Formát výstupu

Vypíšte jeden riadok v ktorom sa nachádza \(n\) medzerami oddelených čísel: postupnosť v ktorom vieme odpájať mestá od elektriny.

V prípade, že existuje viac postupností, vypíšte ľubovoľnú.

Malé varovanie

V prípade, že používate python a rekurziu, nezabudnite, že prednadstavený limit rekurzie v pythone je \(1000\), a pre väčšie hĺbky ju treba manuálne nastaviť v programe cez sys.setrecursionlimit.

Bodovanie a obmedzenia

Existujú štyri testovacie sady, každá za dva body, v ktorých platia nasledovné obmedzenia:

Zároveň, v druhej sade navyše platí, že každé mesto je prepojené káblami s práve dvoma inými mestami.

Príklady

Input:

3 3 1
0 1
1 2
2 0

Output:

0 2 1

Tento vstup by sa mohol nachádzať v druhej sade. Keď odpojím od energie mesto číslo \(0\), elektrina vie medzi elektrárňou (v meste \(1\)) a mestom \(2\) prúdiť cez priamy kábel. Keď následne odpojíme mesto \(2\), v meste \(1\) stále je elektrina, lebo sa v ňom nachádza elektráreň. Napokon, keď vypneme elektráreň, ovplyvní to len to mesto, v ktorom sa nachádza.

Input:

3 2 2
0 1
1 2

Output:

0 1 2

Všimnite si, že nemôžeme najskôr odpojiť mesto \(1\), keďže jediný spôsob, akým sa elektrina vie dostať do mesta \(0\) je cez mesto \(1\).

Input:

2 1 0
0 1

Output:

1 0

Nemáme na výber. Najskôr musíme vypnúť elektrinu v meste bez elektrárne

Input:

1 0 0

Output:

0

Máme jediné mesto, v ktorom je elektráreň.

Input:

8 11 2
1 0
2 0
1 6
7 1
6 7
2 6
3 2
4 5
5 2
3 4
2 1

Output:

0 7 6 1 5 4 3 2

Je možné že pre nejaký vstup existuje viacero správnych riešení. Akékoľvek z nich bude akceptované.