Þetta er fjölumferða verkefni (multi-pass problem).

Í stafrænum skjalasöfnum Kivotos hefur Plana uppgötvað safn dularfullra skráa sem nefnast Tvítempruð Dagbókargögn (Bitemporal Logs). Hver skrá samanstendur af $n$ færslum sem merktar eru frá $1$ til $n$ og mynda rótað tré. Hins vegar eru byggingarskorðurnar ólíkar eftir því hvort tímaflæðið horfir til baka (Rökvísi A) eða fram á við (Rökvísi B):

• Rökvísi A: Tréð hefur rót í færslu $1$; sérhver önnur færsla $i$ á sér foreldri $p_i$ þannig að $p_i < i$.
• Rökvísi B: Tréð hefur rót í færslu $n$; sérhver önnur færsla $i$ á sér foreldri $q_i$ þannig að $q_i > i$.

Til að greina byggingareiginleikana skilgreinir Plana tvær tegundir af færslum:

• Endastöð (Terminal): Færsla sem þjónar ekki sem foreldri neinnar annarrar færslu.
• Miðstöð (Hub): Færsla sem þjónar sem foreldri að minnsta kosti einnar annarrar færslu.

Plana tók eftir fullkominni samhverfu sem kallast Röklegur samhljómur (Logical Resonance). Þessi eiginleiki gildir á milli Rökvísi A skrár og Rökvísi B skrár ef og aðeins ef:

$$\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 hefur sannað stærðfræðilega að fjöldi gildra Rökvísi A skráa og Rökvísi B skráa undir þessari skorðu er nákvæmlega sá sami. Nú felur hún þér að hanna Alheimsþýðingarreglu — gagntæka vörpun (bijection) — til aðumbreyta öðru skráarsniðinu í hitt.

Mat á réttmæti

Lausnin þín er keyrð tvisvar á hverju prófi. Í fyrri keyrslunni þarf lausnin þín að breyta hverri Rökvísi A skrá í Rökvísi B skrá sem uppfyllir skilyrðið um Röklegan samhljóm. Í seinni keyrslunni, þegar gefin er Rökvísi B skrá sem fyrri keyrslan þín bjó til, þarf lausnin þín að endurheimta upprunalegu Rökvísi A skrána nákvæmlega.

Inntak seinni keyrslunnar samanstendur af sömu Rökvísi B skrám og úttakið þitt úr fyrri keyrslunni, hugsanlega í annarri röð. Fyrir hverja Rökvísi B skrá í inntaki seinni keyrslunnar þarftu að prenta samsvarandi Rökvísi A skrá. Lausnin þín telst rétt ef úttakið þitt fyrir sérhverja slíka Rökvísi B skrá er nákvæmlega sama Rökvísi A skrá og bjó hana til í fyrri keyrslunni.

Prófunartól fylgir með til að hjálpa þér að þróa og prófa lausnina þína.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $r$ ($r \in \{1, 2\}$) og $T$ ($1 \le T \le 10^5$), sem tákna númer keyrslu og fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan heiltölu $n$ ($2 \le n \le 10^3$).

Ef $r = 1$ inniheldur önnur línan $n$ heiltölur $p_1, p_2, \dots, p_n$ sem tákna Rökvísi A skrána. Tryggt er að $p_1 = 0$, og fyrir $2 \le i \le n$ er $1 \le p_i < i$ færslan sem færsla $i$ er tengd við. Hér notum við $0$ til að tákna að færsla eigi sér ekkert foreldri (þ.e. hún er rótin).

Annars, ef $r = 2$, inniheldur önnur línan $n$ heiltölur $q_1, q_2, \dots, q_n$ sem tákna Rökvísi B skrána. Tryggt er að $q_n = 0$, og fyrir $1 \le i \le n - 1$ er $i < q_i \le n$ færslan sem færsla $i$ er tengd við.

Tryggt er að summa $n^2$ yfir öll prófunartilvik fari ekki yfir $10^7$.

Úttak

Ef $r = 1$ skal fyrir hvert prófunartilvik prenta $n$ heiltölur aðskildar með bili, $q_1, q_2, \dots, q_n$, sem tákna umbreyttu Rökvísi B skrána. Það verður að gilda að $q_n = 0$, og fyrir $1 \le i \le n - 1$ að $i < q_i \le n$. Eiginleikinn Röklegur samhljómur verður að gilda: færsla $i$ er Endastöð í Rökvísi A ef og aðeins ef færsla $i$ er Miðstöð í Rökvísi B.

Annars, ef $r = 2$, skal fyrir hvert prófunartilvik prenta $n$ heiltölur aðskildar með bili, $p_1, p_2, \dots, p_n$, sem tákna endurheimtu Rökvísi A skrána.

Dæmi

Dæmi 1, Umferð 1

Inntak

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

Úttak

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

Dæmi 1, Umferð 2

Inntak

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

Úttak

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

Skýring á Dæmi 1

Ein möguleg gild gagntæk vörpun er sýnd hér að neðan.