Verkossa on $n$ solmua, jotka on numeroitu $1,2,\ldots,n$. Verkko on puu, joten siinä on $n-1$ kaarta ja minkä tahansa kahden solmun välillä on polku.

Joka siirrolla etsit solmun, josta lähtee vain yksi kaari ja jonka numero on mahdollisimman pieni. Poistat tämän solmun sekä siitä lähtevän kaaren verkosta. Jatkat samaa, kunnes verkossa on vain kaksi solmua.

Kirjaat muistiin joka poiston yhteydessä sen solmun numeron, joka on poistettavan solmun vieressä. Osoittautuu, että verkon rakenteen pystyy palauttamaan näistä kirjauksista, ja se on seuraava tehtäväsi.

Syöte

Syötteessä on ensin kokonaisluku $n$: verkon solmujen määrä.

Sitten syötteessä on $n-2$ lukua, jotka kertovat poistettujen solmujen viereiset solmut.

Tuloste

Tulosta $n-1$ riviä, joista jokainen kuvaa yhden puun kaaren. Voit tulostaa kaaret missä tahansa järjestyksessä.

Rajat

• $3 \le n \le 10^5$

Esimerkki

Syöte:

5
2 2 4

Tuloste:

1 2
2 3
2 4
4 5