Маленькая Голубая Рыбка ведет мастер-класс по структурам данных в Университете Кубка. В традиционных задачах на структуры данных вам обычно предлагается набор запросов и требуется вычислить какое-то сложное выражение на фиксированной структуре данных. Ой, ну правда... кому это нужно в 2026 году? Маленькая Голубая Рыбка хочет чего-то другого. Она просит вас самостоятельно придумать структуру данных.

Ваша задача — построить корневое бинарное дерево $T$: Каждая внутренняя вершина дерева $T$ имеет ровно двух потомков. * $T$ имеет ровно $m$ листьев, помеченных числами от $1$ до $m$.

Рисунок 1: Корректное дерево $T$ для $m = 6$. Каждая внутренняя вершина имеет ровно двух потомков, а листья содержат метки $1, \dots, m$ в некотором порядке. Глубина дерева равна 5.

Для любого множества меток листьев $S$ определим его стоимость в $T$ как количество таких внутренних вершин $v$ дерева $T$, что поддерево вершины $v$ содержит: Хотя бы один лист, метка которого принадлежит $S$. Хотя бы один лист, метка которого не принадлежит $S$.

Маленькая Голубая Рыбка дает вам два корневых дерева $T_1$ и $T_2$. Оба дерева имеют вершины, помеченные числами от $1$ до $n$, и вершина $1$ является корнем каждого из них. Она также дает вам $m$ упорядоченных пар $(x_i, y_i)$, где $x_i$ — вершина дерева $T_1$, а $y_i$ — вершина дерева $T_2$. Лист с меткой $\ell$ в $T$ ассоциирован со значениями $x_\ell$ и $y_\ell$.

Для корневого дерева $T$ и вершины $x$ пусть $\text{path}(T, x)$ — множество вершин на пути от $x$ до корня дерева $T$, включая оба конца.

Маленькая Голубая Рыбка хочет, чтобы вы знали, что для каждой вершины $u$ дерева $T_1$ определяется $Q_1(u) = \{\ell \mid x_\ell \in \text{path}(T_1, u)\}$. Аналогично, для каждой вершины $u$ дерева $T_2$ определяется $Q_2(u) = \{\ell \mid y_\ell \in \text{path}(T_2, u)\}$. Каждое $Q_i(u)$ является множеством меток листьев дерева $T$.

*Лист — это вершина без потомков, а внутренняя вершина — это вершина, которая не является листом.

Рисунок 2: Множество $\text{path}(T_i, x)$ содержит каждую вершину на единственном пути от $x$ до корня, включая оба конца.

Множества, которые проверяет Маленькая Голубая Рыбка, — это $Q_1(u)$ и $Q_2(u)$ для каждого $1 \le u \le n$. Маленькая Голубая Рыбка примет вашу структуру данных, если она удовлетворяет обоим требованиям: глубина каждой вершины в $T$ не превышает 100, где корень имеет глубину 1; среди всех $2n$ проверенных множеств максимальная стоимость не превышает 16 666.

Покажите Маленькой Голубой Рыбке, что вы настоящий мастер структур данных!

Входные данные

Первая строка входных данных содержит два целых числа $n$ и $m$ ($1 \le n, m \le 10^6$).

Следующая строка содержит $n - 1$ целое число $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), описывающих дерево $T_1$. Целое число $p_i$ является родителем вершины $i$ в $T_1$.

Следующая строка содержит $n - 1$ целое число $p'_2, p'_3, \dots, p'_n$ ($1 \le p'_i < i$), описывающих дерево $T_2$. Целое число $p'_i$ является родителем вершины $i$ в $T_2$.

Следующие $m$ строк описывают упорядоченные пары. $i$-я из этих строк содержит два целых числа $x_i$ и $y_i$ ($1 \le x_i, y_i \le n$).

Выходные данные

Выведите одну строку, содержащую последовательность целых чисел, описывающую построенное вами бинарное дерево $T$. Лист с меткой $i$ описывается целым числом $i$. Внутренняя вершина описывается целым числом $0$, за которым следует описание её левого поддерева, а затем описание её правого поддерева.

При таком кодировании каждое целое число от $1$ до $m$ должно встретиться ровно один раз, и каждое вхождение $0$ представляет одну внутреннюю вершину.

Например, последовательность 0 1 0 2 3 описывает дерево, у которого корень имеет лист $1$ в качестве левого потомка и внутреннюю вершину в качестве правого потомка; эта внутренняя вершина имеет листья $2$ и $3$ в качестве своих потомков.

Примеры

Примеры 1

1 1
1 1

1

Примеры 2

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

0 1 0 2 3

Примеры 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

Примечание

Объяснение к примеру 1: Бинарное дерево имеет единственный лист с меткой 1. Его глубина равна 1, и каждый возможный запрос имеет стоимость 0.