Little Cyan Fish prowadzi kurs mistrzowski z zakresu struktur danych na Uniwersytecie Cup. W tradycyjnych zadaniach ze strukturami danych otrzymałbyś teraz stos zapytań i musiałbyś obliczyć jakieś skomplikowane wyrażenie na ustalonej strukturze danych. Och, daj spokój... kto chce to robić w 2026 roku? Little Cyan Fish chce zrobić coś innego. Prosi cię, abyś samodzielnie wymyślił strukturę danych.

Twoim zadaniem jest skonstruowanie ukorzenionego drzewa binarnego $T$: Każdy węzeł wewnętrzny drzewa $T$ ma dokładnie dwoje dzieci. * $T$ ma dokładnie $m$ liści, oznaczonych etykietami od $1$ do $m$.

Rysunek 1: Poprawne $T$ dla $m = 6$. Każdy węzeł wewnętrzny ma dokładnie dwoje dzieci, a liście posiadają etykiety $1, \dots, m$ w pewnej kolejności. Głębokość wynosi tutaj 5.

Dla dowolnego zbioru $S$ etykiet liści, zdefiniuj jego koszt w $T$ jako liczbę takich węzłów wewnętrznych $v$ drzewa $T$, że poddrzewo węzła $v$ zawiera zarówno: Co najmniej jeden liść, którego etykieta należy do $S$. Co najmniej jeden liść, którego etykieta nie należy do $S$.

Little Cyan Fish daje ci dwa ukorzenione drzewa $T_1$ oraz $T_2$. Oba drzewa mają wierzchołki ponumerowane od $1$ do $n$, a wierzchołek $1$ jest korzeniem każdego z nich. Daje ci również $m$ uporządkowanych par $(x_i, y_i)$, gdzie $x_i$ jest wierzchołkiem drzewa $T_1$, a $y_i$ jest wierzchołkiem drzewa $T_2$. Liść oznaczony etykietą $\ell$ w $T$ jest powiązany z wartościami $x_\ell$ oraz $y_\ell$.

Dla ukorzenionego drzewa $T$ i wierzchołka $x$, niech $\text{path}(T, x)$ oznacza zbiór wierzchołków na ścieżce od $x$ do korzenia drzewa $T$, wliczając oba końce.

Little Cyan Fish chce, abyś wiedział, że dla każdego wierzchołka $u$ drzewa $T_1$, definiujemy $Q_1(u) = \{\ell \mid x_\ell \in \text{path}(T_1, u)\}$. Podobnie, dla każdego wierzchołka $u$ drzewa $T_2$, definiujemy $Q_2(u) = \{\ell \mid y_\ell \in \text{path}(T_2, u)\}$. Każde $Q_i(u)$ jest zbiorem etykiet liści drzewa $T$.

*Liść to wierzchołek bez dzieci, a węzeł wewnętrzny to wierzchołek, który nie jest liściem.

Rysunek 2: Zbiór $\text{path}(T_i, x)$ zawiera każdy wierzchołek na unikalnej ścieżce od $x$ do korzenia, wliczając oba końce.

Zbiory, które sprawdza Little Cyan Fish, to $Q_1(u)$ oraz $Q_2(u)$ dla każdego $1 \le u \le n$. Little Cyan Fish zaakceptuje twoją strukturę danych, jeśli spełnia ona oba wymagania: głębokość każdego wierzchołka w $T$ wynosi co najwyżej 100, gdzie korzeń ma głębokość 1; spośród wszystkich $2n$ sprawdzanych zbiorów, maksymalny koszt wynosi co najwyżej 16 666.

Pokaż Little Cyan Fish, że jesteś prawdziwym mistrzem struktur danych!

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 10^6$).

Następna linia wejścia zawiera $n - 1$ liczb całkowitych $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), opisujących drzewo $T_1$. Liczba $p_i$ jest rodzicem wierzchołka $i$ w $T_1$.

Następna linia wejścia zawiera $n - 1$ liczb całkowitych $p'_2, p'_3, \dots, p'_n$ ($1 \le p'_i < i$), opisujących drzewo $T_2$. Liczba $p'_i$ jest rodzicem wierzchołka $i$ w $T_2$.

Następne $m$ linii opisuje uporządkowane pary. $i$-ta z tych linii zawiera dwie liczby całkowite $x_i$ oraz $y_i$ ($1 \le x_i, y_i \le n$).

Wyjście

Wypisz pojedynczą linię zawierającą ciąg liczb całkowitych opisujących skonstruowane przez ciebie drzewo binarne $T$. Liść oznaczony etykietą $i$ jest opisany liczbą całkowitą $i$. Węzeł wewnętrzny jest opisany liczbą całkowitą $0$, po której następuje opis jego lewego poddrzewa, a następnie opis jego prawego poddrzewa.

W tym kodowaniu każda liczba całkowita od $1$ do $m$ musi wystąpić dokładnie raz, a każde wystąpienie $0$ reprezentuje jeden węzeł wewnętrzny.

Na przykład, ciąg $0\ 1\ 0\ 2\ 3$ opisuje drzewo, którego korzeń ma liść $1$ jako lewe dziecko oraz węzeł wewnętrzny jako prawe dziecko; ten węzeł wewnętrzny ma liście $2$ oraz $3$ jako swoje dzieci.

Przykład

Przykład 1

1 1
1 1

1

Przykład 2

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

0 1 0 2 3

Przykład 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

Uwagi

Wyjaśnienie przykładu 1: Drzewo binarne ma pojedynczy liść oznaczony etykietą 1. Jego głębokość wynosi 1, a każde możliwe zapytanie ma koszt 0.