Little Cyan Fish está impartiendo la clase magistral de Estructuras de Datos en la Universidad de Cup. En los problemas tradicionales de estructuras de datos, se te entregaría una pila de consultas y se te pediría evaluar alguna expresión compleja sobre una estructura de datos fija. Oh, vamos... ¿quién quiere hacer eso en 2026? Little Cyan Fish quiere hacer algo diferente. Te pide que inventes la estructura de datos por tu cuenta.

Tu tarea es construir un árbol binario enraizado $T$:

• Cada vértice interno* de $T$ tiene exactamente dos hijos.
• $T$ tiene exactamente $m$ hojas, etiquetadas del 1 al $m$.

Figura 1: Un $T$ válido para $m = 6$. Cada vértice interno tiene exactamente dos hijos, y las hojas llevan las etiquetas $1, \dots, m$ en algún orden. Aquí la profundidad es 5.

Para cualquier conjunto $S$ de etiquetas de hojas, define su costo en $T$ como el número de vértices internos $v$ de $T$ tales que el subárbol de $v$ contiene ambos:

• Al menos una hoja cuya etiqueta pertenece a $S$.
• Al menos una hoja cuya etiqueta no pertenece a $S$.

Little Cyan Fish te da dos árboles enraizados $T_1$ y $T_2$. Ambos árboles tienen vértices etiquetados del 1 al $n$, y el vértice 1 es la raíz de cada árbol. También te da $m$ pares ordenados $(x_i, y_i)$, donde $x_i$ es un vértice de $T_1$ y $y_i$ es un vértice de $T_2$. La hoja etiquetada $\ell$ en $T$ está asociada con los valores $x_\ell$ y $y_\ell$.

Para un árbol enraizado $T$ y un vértice $x$, sea $\text{path}(T, x)$ el conjunto de vértices en el camino desde $x$ hasta la raíz de $T$, incluyendo ambos extremos.

Little Cyan Fish quiere que sepas que, para cada vértice $u$ de $T_1$, se define $Q_1(u) = \{\ell \mid x_\ell \in \text{path}(T_1, u)\}$. De manera similar, para cada vértice $u$ de $T_2$, se define $Q_2(u) = \{\ell \mid y_\ell \in \text{path}(T_2, u)\}$. Cada $Q_i(u)$ es un conjunto de etiquetas de hojas de $T$.

*Una hoja es un vértice sin hijos, y un vértice interno es un vértice que no es una hoja.

Figura 2: El conjunto $\text{path}(T_i, x)$ contiene cada vértice en el camino único desde $x$ hasta la raíz, incluyendo ambos extremos.

Los conjuntos que Little Cyan Fish verifica son $Q_1(u)$ y $Q_2(u)$ para cada $1 \le u \le n$. Little Cyan Fish acepta tu estructura de datos si satisface ambos requisitos:

• La profundidad de cada vértice en $T$ es como máximo 100, donde la raíz tiene profundidad 1.
• Entre todos los $2n$ conjuntos verificados, el costo máximo es como máximo 16 666.

¡Demuéstrale a Little Cyan Fish que eres el verdadero maestro de las estructuras de datos!

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $m$ ($1 \le n, m \le 10^6$).

La siguiente línea de la entrada contiene $n - 1$ enteros $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), que describen el árbol $T_1$. El entero $p_i$ es el padre del vértice $i$ en $T_1$.

La siguiente línea de la entrada contiene $n - 1$ enteros $p'_2, p'_3, \dots, p'_n$ ($1 \le p'_i < i$), que describen el árbol $T_2$. El entero $p'_i$ es el padre del vértice $i$ en $T_2$.

Las siguientes $m$ líneas describen los pares ordenados. La $i$-ésima de estas líneas contiene dos enteros $x_i$ y $y_i$ ($1 \le x_i, y_i \le n$).

Salida

Imprime una sola línea que contenga una secuencia de enteros que describa el árbol binario $T$ que construiste.

• Una hoja etiquetada $i$ se describe con el entero $i$.
• Un vértice interno se describe con el entero 0, seguido por la descripción de su subárbol izquierdo, y luego por la descripción de su subárbol derecho.

Bajo esta codificación, cada entero del 1 al $m$ debe aparecer exactamente una vez, y cada ocurrencia de 0 representa un vértice interno.

Por ejemplo, la secuencia 0 1 0 2 3 describe un árbol cuya raíz tiene a la hoja 1 como su hijo izquierdo y a un vértice interno como su hijo derecho; ese vértice interno tiene a las hojas 2 y 3 como sus hijos.

Ejemplos

Ejemplos 1

1 1
1 1

1

Ejemplos 2

3 3
1 1
1 2
1 1
2 2
3 3

0 1 0 2 3

Ejemplos 3

5 8
1 2 3 4
1 1 1 1
1 1
2 1
3 2
4 2
5 3
5 5
1 5
3 4

0 0 1 0 0 3 8 0 2 7 0 4 0 5 6

Nota

Explicación del Ejemplo 1: El árbol binario tiene una única hoja etiquetada 1. Su profundidad es 1, y cada consulta posible tiene costo 0.