Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Prüfer-koodi


Task | Statistics


CSES - Prüfer-koodiCSES - Prüfer-koodi

Time limit:1.00 s Memory limit:512 MB

Tarkastellaan puuta, jossa on $n$ solmua. Puun Prüfer-koodi on $n-2$ kokonaisluvun jono, joka kuvaa puun rakenteen yksikäsitteisesti.

Muodostamme koodin etsimällä joka vaiheessa puusta lehden, jonka numero on pienin, lisäämällä tämän solmun ainoan naapurin numeron koodiin ja poistamalla solmun puusta. Jatkamme näin niin kauan kuin puussa on ainakin kolme solmua.

Tehtäväsi on palauttaa puun alkuperäinen rakenne Prüfer-koodista.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: solmujen määrä. Solmut on numeroitu $1,2,\dots,n$.

Toisella rivillä on $n-2$ kokonaislukua: puun Prüfer-koodi.

Tuloste

Tulosta $n-1$ riviä, jotka kuvaavat puun solmut. Jokaisella rivillä tulee olla kaksi kokonaislukua $a$ ja $b$: solmujen $a$ ja $b$ välillä on kaari. Voit tulostaa kaaret missä tahansa järjestyksessä.

Rajat
Esimerkki

Syöte:
5
2 2 4


Tuloste:
1 2
2 3
2 4
4 5