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é.