Tämä on monivaiheinen tehtävä (multi-pass problem).

Kivotosin digitaalisista arkistoista Plana on löytänyt kokoelman salaperäisiä tallenteita, jotka tunnetaan Bitemporaalisina Lokeina. Jokainen loki koostuu $n$ merkinnästä, jotka on numeroitu $1$:stä $n$:ään ja jotka muodostavat juurellisen puun. Rakenteelliset rajoitteet kuitenkin eroavat sen mukaan, onko ajan kulku takautuvaa (Logiikka A) vai ennakoivaa (Logiikka B):

• Logiikka A: Puun juuri on merkintä $1$; jokaisella muulla merkinnällä $i$ on vanhempi $p_i$ siten, että $p_i < i$.
• Logiikka B: Puun juuri on merkintä $n$; jokaisella muulla merkinnällä $i$ on vanhempi $q_i$ siten, että $q_i > i$.

Analysoidakseen rakenteellisia ominaisuuksia Plana määrittelee kahdenlaisia merkintöjä:

• Pääte (Terminal): Merkintä, joka ei toimi minkään muun merkinnän vanhempana.
• Keskitin (Hub): Merkintä, joka toimii vähintään yhden muun merkinnän vanhempana.

Plana havaitsi täydellisen symmetrian, jota kutsutaan Loogiseksi resonanssiksi (Logical Resonance). Tämä ominaisuus pätee Logiikan A lokin ja Logiikan B lokin välillä jos ja vain jos:

$$\text{For every } i\text{, entry } i \text{ is a Terminal in Logic A} \iff \text{entry } i \text{ is a Hub in Logic B.}$$

Plana on todistanut matemaattisesti, että kelvollisten Logiikan A lokien ja Logiikan B lokien lukumäärä tämän rajoitteen vallitessa on täsmälleen sama. Nyt hän antaa tehtäväksesi suunnitella Universaalin Käännösprotokollan – bijektion – joka muuntaa lokimuodon toiseksi.

Oikeellisuuden arviointi

Ratkaisuasi ajetaan jokaisessa testissä kahdesti. Ensimmäisellä ajokerralla ratkaisusi on muunnettava jokainen Logiikan A loki Logiikan B lokiksi, joka täyttää Loogisen resonanssin ehdon. Toisella ajokerralla, kun syötteenä annetaan ensimmäisen ajokertasi tuottama Logiikan B loki, ratkaisusi on palautettava täsmälleen alkuperäinen Logiikan A loki.

Toisen ajokerran syöte koostuu samoista Logiikan B lokeista kuin ensimmäisen ajokertasi tuloste, mahdollisesti eri järjestyksessä. Jokaista toisen ajokerran syötteenä annettua Logiikan B lokia kohden sinun on tulostettava sitä vastaava Logiikan A loki. Ratkaisusi katsotaan oikeaksi, jos jokaiselle tällaiselle Logiikan B lokille tulosteesi on täsmälleen sama Logiikan A loki, josta se muodostettiin ensimmäisellä ajokerralla.

Tarjolla on testaustyökalu, jonka avulla voit kehittää ja testata ratkaisuasi.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $r$ ($r \in \{1, 2\}$) ja $T$ ($1 \le T \le 10^5$), jotka esittävät ajokerran numeroa ja testitapausten lukumäärää.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 10^3$).

Jos $r = 1$, toinen rivi sisältää $n$ kokonaislukua $p_1, p_2, \dots, p_n$, jotka esittävät Logiikan A lokia. On taattu, että $p_1 = 0$, ja kaikilla $2 \le i \le n$ luku $1 \le p_i < i$ on merkintä, johon merkintä $i$ on liitetty. Tässä käytämme lukua $0$ osoittamaan, ettei merkinnällä ole vanhempaa (eli se on juuri).

Muussa tapauksessa, jos $r = 2$, toinen rivi sisältää $n$ kokonaislukua $q_1, q_2, \dots, q_n$, jotka esittävät Logiikan B lokia. On taattu, että $q_n = 0$, ja kaikilla $1 \le i \le n - 1$ luku $i < q_i \le n$ on merkintä, johon merkintä $i$ on liitetty.

On taattu, että lukujen $n^2$ summa yli kaikkien testitapausten ei ylitä arvoa $10^7$.

Tuloste

Jos $r = 1$, tulosta jokaista testitapausta kohden $n$ välilyönnein erotettua kokonaislukua $q_1, q_2, \dots, q_n$, jotka esittävät muunnettua Logiikan B lokia. On pädettävä $q_n = 0$, ja kaikilla $1 \le i \le n - 1$ on pädettävä $i < q_i \le n$. Loogisen resonanssin ominaisuuden on pädettävä: merkintä $i$ on Pääte Logiikassa A jos ja vain jos merkintä $i$ on Keskitin Logiikassa B.

Muussa tapauksessa, jos $r = 2$, tulosta jokaista testitapausta kohden $n$ välilyönnein erotettua kokonaislukua $p_1, p_2, \dots, p_n$, jotka esittävät palautettua Logiikan A lokia.

Esimerkki

Esimerkki 1, Vaihe 1

Syöte

1 3
4
0 1 1 2
4
0 1 2 1
4
0 1 1 1

Tuloste

3 3 4 0
3 4 4 0
2 3 4 0

Esimerkki 1, Vaihe 2

Syöte

2 3
4
2 3 4 0
4
3 3 4 0
4
3 4 4 0

Tuloste

0 1 1 1
0 1 1 2
0 1 2 1

Esimerkin 1 selitys

Alla on esitetty eräs mahdollinen kelvollinen bijektio.