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

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

Esimerkki

Syöte:

5
2 2 4

Tuloste:

1 2
2 3
2 4
4 5