Problem B
Orienteret gennemløb
Languages
da
en
Et orienteret gennemløb af et polygon er rækkefølgen af dets hjørner i den orden, man møder dem, når man starter i et hjørne og følger randen i en fast retning, indtil man vender tilbage til startpunktet.
Du får givet et simpelt polygon med $n$ hjørner. Hjørnerne er mærket med $1,\dots ,n$, men — i modsætning til hvad man måske skulle forvente — er disse mærker ikke nødvendigvis i orienteret gennemløbsorden. I stedet består indlæsningen af en uordnet samling af $n$ forskellige linjestykker, der tilsammen udgør polygonets rand.
Hvert linjestykke forbinder to hjørner, angivet som et uordnet par $\{ a_i,b_i\} $ for $i\in \{ 1,\ldots ,n\} $. Din opgave er at opremse hjørnerne i orienteret gennemløbsorden, altså i den rækkefølge de optræder, når man følger kæden hele vejen rundt én gang, startende og sluttende i hjørne $1$. Især skal hvert efterfølgende par af hjørner i din liste være et af de givne linjestykker. Bemærk, at linjestykket $\{ a_i,b_i\} $ kan bruges til at komme fra $a_i$ til $b_i$ eller fra $b_i$ til $a_i$.
For eksempel danner de fire linjestykker $\{ 1,2\} $, $\{ 1,3\} $, $\{ 2,4\} $ og $\{ 3,4\} $ et polygon, og ved at følge randen fås det orienterede gennemløb $1,2,4,3,1$. Tilsvarende danner de seks linjestykker $\{ 1,4\} $, $\{ 1,5\} $, $\{ 2,3\} $, $\{ 2,5\} $, $\{ 3,6\} $ og $\{ 4,6\} $ et polygon med den orienterede gennemløb $1$, $4$, $6$, $3$, $2$, $5$, $1$. Vi kan illustrere disse eksempler som vist nedenfor; her ville hjørnerne være blevet gennemløbet mod uret, men bemærk, at polygonets geometriske form og den valgte omdrejningsretning faktisk er uden betydning for opgaven:
For at være helt formel er opgaven at finde en ordning $p_1, p_2, \ldots , p_n, p_1$ af hjørnerne med $p_1=1$, så der gælder
\[ \Big\{ \, \{ p_1,p_2\} ,\, \{ p_2,p_3\} ,\, \ldots ,\, \{ p_{n-1},p_n\} ,\, \{ p_n,p_1\} \, \Big\} = \Big\{ \, \{ a_1,b_1\} ,\, \{ a_2,b_2\} ,\, \ldots ,\, \{ a_n,b_n\} \, \Big\} \, . \]Input
Indlæsningen består af:
-
Én linje med et heltal $n\in \{ 3,\ldots ,100\, 000\} $, antallet af linjestykker.
-
$n$ linjer, én for hvert linjestykke. Den $i$’te linje indeholder hjørnerne $a_i$ og $b_i$ med $1\leq a_i<b_i\leq n$. Linjestykkerne er givet i vilkårlig rækkefølge. Hvert hjørne forekommer præcis to gange.
Output
Skriv hjørnerne i orienteret gennemløbsorden, begyndende og sluttende med $1$. Hvis der findes flere gyldige løsninger, må du udskrive en hvilken som helst af dem.
| 1 | 1 |
|---|---|
4 1 2 2 4 1 3 3 4 |
1 2 4 3 1 |
| 2 | 2 |
|---|---|
6 1 4 1 5 2 3 2 5 3 6 4 6 |
1 4 6 3 2 5 1 |
