Este es un problema de múltiples pasadas.

En los archivos digitales de Kivotos, Plana ha descubierto una colección de registros misteriosos conocidos como Registros Bitemporales. Cada registro consiste en $n$ entradas etiquetadas de $1$ a $n$ que forman un árbol enraizado. Sin embargo, las restricciones estructurales difieren dependiendo de si el flujo temporal es retrospectivo (Lógica A) o prospectivo (Lógica B):

• Lógica A: El árbol está enraizado en la entrada $1$; cada otra entrada $i$ tiene un padre $p_i$ tal que $p_i < i$.
• Lógica B: El árbol está enraizado en la entrada $n$; cada otra entrada $i$ tiene un padre $q_i$ tal que $q_i > i$.

Para analizar las propiedades estructurales, Plana define dos tipos de entradas:

• Terminal: Una entrada que no sirve como padre de ninguna otra entrada.
• Hub: Una entrada que sirve como padre de al menos otra entrada.

Plana observó una simetría perfecta llamada Resonancia Lógica. Esta propiedad se cumple entre un registro de Lógica A y un registro de Lógica B si y solo si:

Para todo $i$, la entrada $i$ es una Terminal en Lógica A $\iff$ la entrada $i$ es un Hub en Lógica B.

Plana ha demostrado matemáticamente que el número de registros de Lógica A y Lógica B válidos bajo esta restricción es idéntico. Ahora, te encarga diseñar un Protocolo de Traducción Universal —una biyección— para transformar un formato de registro en el otro.

Nota: tu solución será evaluada como un procedimiento interactivo en cualquiera de las ejecuciones.

Evaluación de la corrección

Tu solución se ejecuta dos veces en cada prueba. En la primera ejecución, tu solución debe convertir cada registro de Lógica A en un registro de Lógica B que satisfaga la condición de Resonancia Lógica. En la segunda ejecución, dado un registro de Lógica B producido por tu primera ejecución, tu solución debe recuperar exactamente el registro de Lógica A original.

La entrada de la segunda ejecución consiste en los mismos registros de Lógica B que tu salida de la primera ejecución, posiblemente en un orden diferente. Para cada registro de Lógica B de entrada en la segunda ejecución, debes generar su registro de Lógica A correspondiente. Tu solución se considera correcta si, para cada uno de esos registros de Lógica B, tu salida es exactamente el mismo registro de Lógica A que lo generó en la primera ejecución.

Se proporciona una herramienta de prueba para ayudarte a desarrollar y probar tu solución.

Entrada

La primera línea de la entrada contiene dos enteros $r$ ($r \in \{1, 2\}$) y $T$ ($1 \le T \le 10^5$), que representan el número de ejecución y el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero $n$ ($2 \le n \le 10^3$).

Si $r = 1$, la segunda línea contiene $n$ enteros $p_1, p_2, \dots, p_n$ que representan el registro de Lógica A. Se garantiza que $p_1 = 0$, y para $2 \le i \le n$, $1 \le p_i < i$ es la entrada a la que está unida la entrada $i$. Aquí usamos $0$ para denotar que una entrada no tiene padre (es decir, es la raíz).

De lo contrario, si $r = 2$, la segunda línea contiene $n$ enteros $q_1, q_2, \dots, q_n$ que representan el registro de Lógica B. Se garantiza que $q_n = 0$, y para $1 \le i \le n - 1$, $i < q_i \le n$ es la entrada a la que está unida la entrada $i$.

Se garantiza que la suma de $n^2$ sobre todos los casos de prueba no excede $10^7$.

Salida

Si $r = 1$, para cada caso de prueba, imprime $n$ enteros separados por un espacio, $q_1, q_2, \dots, q_n$, que representan el registro de Lógica B convertido. Debe cumplirse que $q_n = 0$, y para $1 \le i \le n - 1$, $i < q_i \le n$. La propiedad de Resonancia Lógica debe cumplirse: la entrada $i$ es una Terminal en Lógica A si y solo si la entrada $i$ es un Hub en Lógica B.

De lo contrario, si $r = 2$, para cada caso de prueba, imprime $n$ enteros separados por un espacio, $p_1, p_2, \dots, p_n$, que representan el registro de Lógica A restaurado.

Ejemplos

Entrada 1 (Ejecución 1)

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

Salida 1 (Ejecución 1)

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

Entrada 2 (Ejecución 2)

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

Salida 2 (Ejecución 2)

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

Nota

Explicación del Ejemplo 1: Se muestra a continuación una posible biyección válida.

Lógica A y Lógica B