CSES - Prüfer-koodi
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tarkastellaan puuta, jossa on nn solmua. Puun Prüfer-koodi on n2n-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 nn: solmujen määrä. Solmut on numeroitu 1,2,,n1,2,\dots,n.

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

Tuloste

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

Rajat

  • 3n51053 \le n \le 5 \cdot 10^5
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

5
2 2 4

Tuloste:

1 2
2 3
2 4
4 5