Ceci est un problème multi-passes.

Dans les archives numériques de Kivotos, Plana a découvert une collection de documents mystérieux appelés Journaux Bitemporels. Chaque journal consiste en $n$ entrées étiquetées de $1$ à $n$ formant un arbre enraciné. Cependant, les contraintes structurelles diffèrent selon que le flux temporel est rétrospectif (Logique A) ou prospectif (Logique B) :

• Logique A : L'arbre est enraciné à l'entrée $1$ ; chaque autre entrée $i$ a un parent $p_i$ tel que $p_i < i$.
• Logique B : L'arbre est enraciné à l'entrée $n$ ; chaque autre entrée $i$ a un parent $q_i$ tel que $q_i > i$.

Pour analyser les propriétés structurelles, Plana définit deux types d'entrées :

• Terminal : Une entrée qui ne sert de parent à aucune autre entrée.
• Hub : Une entrée qui sert de parent à au moins une autre entrée.

Plana a observé une symétrie parfaite appelée Résonance Logique. Cette propriété est vérifiée entre un journal Logique A et un journal Logique B si et seulement si :

Pour tout $i$, l'entrée $i$ est un Terminal en Logique A $\iff$ l'entrée $i$ est un Hub en Logique B.

Plana a prouvé mathématiquement que le nombre de journaux Logique A et Logique B valides sous cette contrainte est identique. Maintenant, elle vous charge de concevoir un Protocole de Traduction Universel — une bijection — pour transformer un format de journal en l'autre.

Remarque : votre solution sera évaluée en tant que procédure interactive lors de chacune des exécutions.

Évaluation de la correction

Votre solution est exécutée deux fois sur chaque test. Lors de la première exécution, votre solution doit convertir chaque journal Logique A en un journal Logique B qui satisfait la condition de Résonance Logique. Lors de la seconde exécution, étant donné un journal Logique B produit par votre première exécution, votre solution doit récupérer exactement le journal Logique A original.

L'entrée de la seconde exécution consiste en les mêmes journaux Logique B que votre sortie de la première exécution, possiblement dans un ordre différent. Pour chaque journal Logique B en entrée lors de la seconde exécution, vous devez afficher son journal Logique A correspondant. Votre solution est considérée comme correcte si, pour chaque journal Logique B, votre sortie est exactement le même journal Logique A qui l'a généré lors de la première exécution.

Un outil de test est fourni pour vous aider à développer et tester votre solution.

Entrée

La première ligne de l'entrée contient deux entiers $r$ ($r \in \{1, 2\}$) et $T$ ($1 \le T \le 10^5$), représentant le numéro de l'exécution et le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier $n$ ($2 \le n \le 10^3$).

Si $r = 1$, la deuxième ligne contient $n$ entiers $p_1, p_2, \dots, p_n$ représentant le journal Logique A. Il est garanti que $p_1 = 0$, et pour $2 \le i \le n$, $1 \le p_i < i$ est l'entrée à laquelle l'entrée $i$ est rattachée. Ici, nous utilisons $0$ pour indiquer qu'une entrée n'a pas de parent (c'est-à-dire la racine).

Sinon, si $r = 2$, la deuxième ligne contient $n$ entiers $q_1, q_2, \dots, q_n$ représentant le journal Logique B. Il est garanti que $q_n = 0$, et pour $1 \le i \le n - 1$, $i < q_i \le n$ est l'entrée à laquelle l'entrée $i$ est rattachée.

Il est garanti que la somme des $n^2$ sur tous les cas de test n'excède pas $10^7$.

Sortie

Si $r = 1$, pour chaque cas de test, affichez $n$ entiers séparés par un espace, $q_1, q_2, \dots, q_n$, représentant le journal Logique B converti. Il doit être vérifié que $q_n = 0$, et pour $1 \le i \le n - 1$, $i < q_i \le n$. La propriété de Résonance Logique doit être respectée : l'entrée $i$ est un Terminal en Logique A si et seulement si l'entrée $i$ est un Hub en Logique B.

Sinon, si $r = 2$, pour chaque cas de test, affichez $n$ entiers séparés par un espace, $p_1, p_2, \dots, p_n$, représentant le journal Logique A restauré.

Exemples

Entrée 1 (Pass 1)

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

Sortie 1 (Pass 1)

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

Entrée 2 (Pass 2)

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

Sortie 2 (Pass 2)

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

Remarque

Explication de l'exemple 1 : Une bijection valide possible est illustrée ci-dessous.

Logique A et Logique B