Problem J
Jaðarjuð

Mynd eftir Randall Munroe, xkcd.com

Síðustu ár hefur verið umræða um að sameina suma háskóla á Íslandi. Nú er loks verið að leggja drög að því hvernig mætti fara að því, en til að smíða góð plön þarf skipulagsnefndin að geta fengið upplýsingar um hvernig ferlið myndi fara jafn óðum. Eftir að hafa frétt af þessarri forritunarkeppni og tuðað einstaklega lengi í dómnefnd hennar er samþykkt að láta keppendur sjá um þetta mátulega skemmtilega verk.

Inntak

Inntakið byrjar á línu með tveimur heiltölum $n$, fjöldi háskóla, og $q$ sem gefur fjölda aðgerða. Gefið er að $1\le n,q\le 5\cdot {10}^5$. Næst koma $q$ línur þar sem hver þeirra lýsir einni aðgerð. Hver þeirra byrjar á einum staf sem er j, u eða p. Ef línan byrjar á j koma næst tvær tölur $1\le a,b\le n$ með $a\ne b$ sem gefur að sameina eigi háskóla $a$ og háskóla $b$. Ef línan byrjar á u á að afturkalla síðustu sameiningu. Ef engin sameining er til staðar til að afturkalla skal aðgerðin gera ekkert. Loks ef línan byrjar á p kemur næst ein heiltala $1\le a\le n$ og prenta á þá númer allra háskóla sem búið er að sameina við háskóla númer $a$, með $a$ sjálfum meðtöldum. Athugið að ef $a$ er sameinað við $b$ og $b$ við $c$ þá teljum við sem svo að $a$ hafi sameinast við $c$.

Úttak

Fyrir hverja aðgerð sem byrjar á p á að prenta eina línu af heiltölum eins og lýst er að ofan. Tölurnar skulu vera aðskilnar með bilum, en prenta má tölurnar í hvaða innbyrðis röð sem er á línunni. Prenta á línurnar í sömu röð og aðgerðirnar eru gefnar í inntaki. Gefið er að mest þurfi að prenta ${10}^6$ tölur.

4 11
p 3
j 1 2
j 3 4
p 2
j 1 3
j 1 2
p 2
u
u
u
p 4

3 
1 2 
1 2 3 4 
4