- Time limit: 1.00 s
- Memory limit: 512 MB
Tarkastellaan puuta, jossa on solmua. Puun Prüfer-koodi on 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 : solmujen määrä. Solmut on numeroitu .
Toisella rivillä on kokonaislukua: puun Prüfer-koodi.
Tuloste
Tulosta riviä, jotka kuvaavat puun solmut. Jokaisella rivillä tulee olla kaksi kokonaislukua ja : solmujen ja 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