Detta är ett flerstegsproblem (multi-pass problem).

I Kivotos digitala arkiv har Plana upptäckt en samling mystiska opteckningar som kallas Bitemporala Loggar. Varje logg består av $n$ poster numrerade $1$ till $n$ som bildar ett rotat träd. De strukturella villkoren skiljer sig dock åt beroende på om tidsflödet är retrospektivt (Logik A) eller prospektivt (Logik B):

• Logik A: Trädet är rotat i post $1$; varje annan post $i$ har en förälder $p_i$ sådan att $p_i < i$.
• Logik B: Trädet är rotat i post $n$; varje annan post $i$ har en förälder $q_i$ sådan att $q_i > i$.

För att analysera de strukturella egenskaperna definierar Plana två typer av poster:

• Terminal: En post som inte fungerar som förälder till några andra poster.
• Hubb (Hub): En post som fungerar som förälder till minst en annan post.

Plana observerade en perfekt symmetri som kallas Logisk Resonans (Logical Resonance). Denna egenskap gäller mellan en Logik A-logg och en Logik B-logg om och endast om:

$$\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 matematiskt bevisat att antalet giltiga Logik A-loggar och Logik B-loggar under detta villkor är identiskt. Nu ger hon dig i uppdrag att konstruera ett Universellt Översättningsprotokoll — en bijektion — för att omvandla det ena loggformatet till det andra.

Utvärdering av korrekthet

Din lösning körs två gånger på varje test. I den första körningen måste din lösning omvandla varje Logik A-logg till en Logik B-logg som uppfyller villkoret för Logisk Resonans. I den andra körningen, givet en Logik B-logg som producerats av din första körning, måste din lösning exakt återskapa den ursprungliga Logik A-loggen.

Indatan i den andra körningen består av samma Logik B-loggar som din utdata från den första körningen, eventuellt i en annan ordning. För varje Logik B-logg i indatan i den andra körningen måste du skriva ut dess motsvarande Logik A-logg. Din lösning betraktas som korrekt om din utdata för varje sådan Logik B-logg är exakt samma Logik A-logg som genererade den i den första körningen.

Ett testverktyg tillhandahålls för att hjälpa dig att utveckla och testa din lösning.

Indata

Den första raden i indatan innehåller två heltal $r$ ($r \in \{1, 2\}$) och $T$ ($1 \le T \le 10^5$), som representerar körningsnumret och antalet testfall.

För varje testfall innehåller den första raden ett heltal $n$ ($2 \le n \le 10^3$).

Om $r = 1$ innehåller den andra raden $n$ heltal $p_1, p_2, \dots, p_n$ som representerar Logik A-loggen. Det garanteras att $p_1 = 0$, och för $2 \le i \le n$ är $1 \le p_i < i$ den post som post $i$ är fäst vid. Här använder vi $0$ för att ange att en post saknar förälder (dvs. den är roten).

Annars, om $r = 2$, innehåller den andra raden $n$ heltal $q_1, q_2, \dots, q_n$ som representerar Logik B-loggen. Det garanteras att $q_n = 0$, och för $1 \le i \le n - 1$ är $i < q_i \le n$ den post som post $i$ är fäst vid.

Det garanteras att summan av $n^2$ över alla testfall inte överstiger $10^7$.

Utdata

Om $r = 1$, skriv för varje testfall ut $n$ heltal separerade med mellanslag, $q_1, q_2, \dots, q_n$, som representerar den omvandlade Logik B-loggen. Det måste gälla att $q_n = 0$, och för $1 \le i \le n - 1$ att $i < q_i \le n$. Egenskapen Logisk Resonans måste gälla: post $i$ är en Terminal i Logik A om och endast om post $i$ är en Hubb i Logik B.

Annars, om $r = 2$, skriv för varje testfall ut $n$ heltal separerade med mellanslag, $p_1, p_2, \dots, p_n$, som representerar den återställda Logik A-loggen.

Exempel

Exempel 1, Omgång 1

Indata

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

Exempel 1, Omgång 2

Indata

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

Förklaring av Exempel 1

En möjlig giltig bijektion visas nedan.