Dies ist ein Multi-Pass-Problem.

In den digitalen Archiven von Kivotos hat Plana eine Sammlung mysteriöser Aufzeichnungen entdeckt, die als Bitemporale Logs bekannt sind. Jedes Log besteht aus $n$ Einträgen mit den Nummern $1$ bis $n$, die einen gewurzelten Baum bilden. Allerdings unterscheiden sich die strukturellen Bedingungen je nachdem, ob der zeitliche Fluss retrospektiv (Logik A) oder prospektiv (Logik B) ist:

• Logik A: Der Baum ist bei Eintrag $1$ gewurzelt; jeder andere Eintrag $i$ hat einen Elternknoten $p_i$ mit $p_i < i$.
• Logik B: Der Baum ist bei Eintrag $n$ gewurzelt; jeder andere Eintrag $i$ hat einen Elternknoten $q_i$ mit $q_i > i$.

Um die strukturellen Eigenschaften zu analysieren, definiert Plana zwei Arten von Einträgen:

• Terminal: Ein Eintrag, der für keinen anderen Eintrag als Elternknoten dient.
• Hub: Ein Eintrag, der für mindestens einen anderen Eintrag als Elternknoten dient.

Plana beobachtete eine perfekte Symmetrie namens Logische Resonanz (Logical Resonance). Diese Eigenschaft gilt zwischen einem Logik-A-Log und einem Logik-B-Log genau dann, wenn:

$$\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 hat mathematisch bewiesen, dass die Anzahl gültiger Logik-A-Logs und Logik-B-Logs unter dieser Bedingung identisch ist. Nun beauftragt sie Sie mit dem Entwurf eines Universellen Übersetzungsprotokolls — einer Bijektion —, um das eine Log-Format in das andere zu überführen.

Bewertung der Korrektheit

Ihre Lösung wird bei jedem Test zweimal ausgeführt. Im ersten Durchlauf muss Ihre Lösung jedes Logik-A-Log in ein Logik-B-Log umwandeln, das die Bedingung der Logischen Resonanz erfüllt. Im zweiten Durchlauf muss Ihre Lösung aus einem vom ersten Durchlauf erzeugten Logik-B-Log wieder exakt das ursprüngliche Logik-A-Log rekonstruieren.

Die Eingabe des zweiten Durchlaufs besteht aus denselben Logik-B-Logs wie Ihre Ausgabe aus dem ersten Durchlauf, möglicherweise in einer anderen Reihenfolge. Für jedes eingegebene Logik-B-Log im zweiten Durchlauf müssen Sie das zugehörige Logik-A-Log ausgeben. Ihre Lösung gilt als korrekt, wenn Ihre Ausgabe für jedes solche Logik-B-Log exakt mit dem Logik-A-Log übereinstimmt, aus dem es im ersten Durchlauf erzeugt wurde.

Ein Testwerkzeug wird bereitgestellt, um Ihnen bei der Entwicklung und dem Testen Ihrer Lösung zu helfen.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $r$ ($r \in \{1, 2\}$) und $T$ ($1 \le T \le 10^5$), die die Durchlaufnummer und die Anzahl der Testfälle angeben.

Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($2 \le n \le 10^3$).

Wenn $r = 1$ ist, enthält die zweite Zeile $n$ ganze Zahlen $p_1, p_2, \dots, p_n$, die das Logik-A-Log darstellen. Es wird garantiert, dass $p_1 = 0$ gilt und für $2 \le i \le n$ der Wert $1 \le p_i < i$ den Eintrag angibt, an den Eintrag $i$ angehängt ist. Hier verwenden wir $0$, um anzugeben, dass ein Eintrag keinen Elternknoten hat (d. h., er ist die Wurzel).

Andernfalls, wenn $r = 2$ ist, enthält die zweite Zeile $n$ ganze Zahlen $q_1, q_2, \dots, q_n$, die das Logik-B-Log darstellen. Es wird garantiert, dass $q_n = 0$ gilt und für $1 \le i \le n - 1$ der Wert $i < q_i \le n$ den Eintrag angibt, an den Eintrag $i$ angehängt ist.

Es wird garantiert, dass die Summe von $n^2$ über alle Testfälle $10^7$ nicht überschreitet.

Ausgabe

Wenn $r = 1$ ist, geben Sie für jeden Testfall $n$ durch Leerzeichen getrennte ganze Zahlen $q_1, q_2, \dots, q_n$ aus, die das umgewandelte Logik-B-Log darstellen. Es muss $q_n = 0$ und für $1 \le i \le n - 1$ die Bedingung $i < q_i \le n$ gelten. Zudem muss die Eigenschaft der Logischen Resonanz erfüllt sein: Eintrag $i$ ist genau dann ein Terminal in Logik A, wenn Eintrag $i$ ein Hub in Logik B ist.

Andernfalls, wenn $r = 2$ ist, geben Sie für jeden Testfall $n$ durch Leerzeichen getrennte ganze Zahlen $p_1, p_2, \dots, p_n$ aus, die das wiederhergestellte Logik-A-Log darstellen.

Beispiel

Beispiel 1, Durchgang 1

Eingabe

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

Ausgabe

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

Beispiel 1, Durchgang 2

Eingabe

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

Ausgabe

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

Erklärung zu Beispiel 1

Eine mögliche gültige Bijektion ist unten dargestellt.