Dette er et flertrinnsproblem (multi-pass problem).

I de digitale arkivene i Kivotos har Plana oppdaget en samling mystiske opptegnelser kjent som Bitemporale Logger. Hver logg består av $n$ oppføringer merket fra $1$ til $n$ som danner et rotfestet tre. De strukturelle kravene varierer imidlertid avhengig av om tidsflyten er retrospektiv (Logikk A) eller prospektiv (Logikk B):

• Logikk A: Treet har rot i oppføring $1$; hver annen oppføring $i$ har en forelder $p_i$ slik at $p_i < i$.
• Logikk B: Treet har rot i oppføring $n$; hver annen oppføring $i$ har en forelder $q_i$ slik at $q_i > i$.

For å analysere de strukturelle egenskapene definerer Plana to typer oppføringer:

• Terminal: En oppføring som ikke fungerer som forelder til noen andre oppføringer.
• Knutepunkt (Hub): En oppføring som fungerer som forelder til minst én annen oppføring.

Plana observerte en perfekt symmetri kalt Logisk Resonans (Logical Resonance). Denne egenskapen gjelder mellom en Logikk A-logg og en Logikk B-logg hvis og bare hvis:

$$\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 har matematisk bevist at antallet gyldige Logikk A-logger og Logikk B-logger under denne betingelsen er identisk. Nå gir hun deg i oppdrag å utforme en Universell Oversettelsesprotokoll — en bijeksjon — for å gjøre om det ene loggformatet til det andre.

Evaluering av korrekthet

Løsningen din kjøres to ganger på hver test. I den første kjøringen må løsningen din konvertere hver Logikk A-logg til en Logikk B-logg som tilfredsstiller kravet om Logisk Resonans. I den andre kjøringen, gitt en Logikk B-logg produsert av den første kjøringen din, må løsningen din gjenopprette den opprinnelige Logikk A-loggen nøyaktig.

Inndataene i den andre kjøringen består av de samme Logikk B-loggene som utdataene dine fra den første kjøringen, muligens i en annen rekkefølge. For hver Logikk B-logg i inndataene i den andre kjøringen må du skrive ut den tilhørende Logikk A-loggen. Løsningen din regnes som riktig dersom utdataen din for hver slik Logikk B-logg er nøyaktig den samme Logikk A-loggen som genererte den i den første kjøringen.

Et testverktøy er tilgjengelig for å hjelpe deg med å utvikle og teste løsningen din.

Inndata

Den første linjen i inndataene inneholder to heltall $r$ ($r \in \{1, 2\}$) og $T$ ($1 \le T \le 10^5$), som representerer kjøringsnummeret og antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen et heltall $n$ ($2 \le n \le 10^3$).

Hvis $r = 1$, inneholder den andre linjen $n$ heltall $p_1, p_2, \dots, p_n$ som representerer Logikk A-loggen. Det garanteres at $p_1 = 0$, og for $2 \le i \le n$ er $1 \le p_i < i$ oppføringen som oppføring $i$ er festet til. Her bruker vi $0$ for å angi at en oppføring ikke har noen forelder (dvs. at den er roten).

Ellers, hvis $r = 2$, inneholder den andre linjen $n$ heltall $q_1, q_2, \dots, q_n$ som representerer Logikk B-loggen. Det garanteres at $q_n = 0$, og for $1 \le i \le n - 1$ er $i < q_i \le n$ oppføringen som oppføring $i$ er festet til.

Det garanteres at summen av $n^2$ over alle testtilfeller ikke overstiger $10^7$.

Utdata

Hvis $r = 1$, skal du for hvert testtilfelle skrive ut $n$ heltall atskilt med mellomrom, $q_1, q_2, \dots, q_n$, som representerer den konverterte Logikk B-loggen. Det må gjelde at $q_n = 0$, og for $1 \le i \le n - 1$ at $i < q_i \le n$. Egenskapen Logisk Resonans må gjelde: oppføring $i$ er en Terminal i Logikk A hvis og bare hvis oppføring $i$ er et Knutepunkt i Logikk B.

Ellers, hvis $r = 2$, skal du for hvert testtilfelle skrive ut $n$ heltall atskilt med mellomrom, $p_1, p_2, \dots, p_n$, som representerer den gjenopprettede Logikk A-loggen.

Eksempel

Eksempel 1, Omgang 1

Inndata

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

Utdata

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

Eksempel 1, Omgang 2

Inndata

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

Utdata

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

Forklaring av Eksempel 1

En mulig gyldig bijeksjon er vist nedenfor.