Little Cyan Fish enseigne le cours magistral sur les structures de données à l'Université de Cup. Dans les problèmes de structures de données traditionnels, on vous donnerait une pile de requêtes et on vous demanderait d'évaluer une expression complexe sur une structure de données fixe. Oh, allez... qui veut faire ça en 2026 ? Little Cyan Fish veut faire quelque chose de différent. Il vous demande d'inventer la structure de données vous-même.

Votre tâche est de construire un arbre binaire enraciné $T$ :

• Chaque sommet interne* de $T$ a exactement deux enfants.
• $T$ possède exactement $m$ feuilles, étiquetées de $1$ à $m$.

Figure 1 : Un $T$ valide pour $m = 6$. Chaque sommet interne a exactement deux enfants, et les feuilles portent les étiquettes $1, \dots, m$ dans un certain ordre. Ici, la profondeur est de 5.

Pour tout ensemble $S$ d'étiquettes de feuilles, définissez son coût sur $T$ comme le nombre de sommets internes $v$ de $T$ tels que le sous-arbre de $v$ contient à la fois :

• Au moins une feuille dont l'étiquette appartient à $S$.
• Au moins une feuille dont l'étiquette n'appartient pas à $S$.

Little Cyan Fish vous donne deux arbres enracinés $T_1$ et $T_2$. Les deux arbres ont des sommets étiquetés de $1$ à $n$, et le sommet $1$ est la racine de chaque arbre. Il vous donne également $m$ paires ordonnées $(x_i, y_i)$, où $x_i$ est un sommet de $T_1$ et $y_i$ est un sommet de $T_2$. La feuille étiquetée $\ell$ dans $T$ est associée aux valeurs $x_\ell$ et $y_\ell$.

Pour un arbre enraciné $T$ et un sommet $x$, soit $\text{path}(T, x)$ l'ensemble des sommets sur le chemin allant de $x$ à la racine de $T$, en incluant les deux extrémités.

Little Cyan Fish veut que vous sachiez que, pour chaque sommet $u$ de $T_1$, on définit $Q_1(u) = \{\ell \mid x_\ell \in \text{path}(T_1, u)\}$. De même, pour chaque sommet $u$ de $T_2$, on définit $Q_2(u) = \{\ell \mid y_\ell \in \text{path}(T_2, u)\}$. Chaque $Q_i(u)$ est un ensemble d'étiquettes de feuilles de $T$.

*Un sommet est une feuille s'il n'a pas d'enfants, et un sommet interne est un sommet qui n'est pas une feuille.

Figure 2 : L'ensemble $\text{path}(T_i, x)$ contient chaque sommet sur le chemin unique allant de $x$ jusqu'à la racine, en incluant les deux extrémités.

Les ensembles que Little Cyan Fish vérifie sont $Q_1(u)$ et $Q_2(u)$ pour tout $1 \le u \le n$. Little Cyan Fish accepte votre structure de données si elle satisfait aux deux exigences suivantes :

• la profondeur de chaque sommet dans $T$ est au plus $100$, où la racine a une profondeur de $1$ ;
• parmi tous les $2n$ ensembles vérifiés, le coût maximal est au plus $16\,666$.

Montrez à Little Cyan Fish que vous êtes le véritable maître des structures de données !

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $m$ ($1 \le n, m \le 10^6$).

La ligne suivante de l'entrée contient $n - 1$ entiers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), décrivant l'arbre $T_1$. L'entier $p_i$ est le parent du sommet $i$ dans $T_1$.

La ligne suivante de l'entrée contient $n - 1$ entiers $p'_2, p'_3, \dots, p'_n$ ($1 \le p'_i < i$), décrivant l'arbre $T_2$. L'entier $p'_i$ est le parent du sommet $i$ dans $T_2$.

Les $m$ lignes suivantes décrivent les paires ordonnées. La $i$-ième de ces lignes contient deux entiers $x_i$ et $y_i$ ($1 \le x_i, y_i \le n$).

Sortie

Affichez une seule ligne contenant une séquence d'entiers qui décrit l'arbre binaire $T$ que vous construisez.

• Une feuille étiquetée $i$ est décrite par l'entier $i$.
• Un sommet interne est décrit par l'entier $0$, suivi de la description de son sous-arbre gauche, puis par la description de son sous-arbre droit.

Selon ce codage, chaque entier de $1$ à $m$ doit apparaître exactement une fois, et chaque occurrence de $0$ représente un sommet interne.

Par exemple, la séquence 0 1 0 2 3 décrit un arbre dont la racine a la feuille $1$ comme enfant gauche et un sommet interne comme enfant droit ; ce sommet interne a les feuilles $2$ et $3$ comme enfants.

Exemples

Exemples 1

1 1
1 1

1

Exemples 2

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

0 1 0 2 3

Exemples 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

Remarque

Explication de l'exemple 1 : L'arbre binaire possède une seule feuille étiquetée $1$. Sa profondeur est de $1$, et chaque requête possible a un coût de $0$.