Little Cyan Fish 正在 Cup 大学教授数据结构大师班。在传统的数据结构问题中，你通常会收到一堆查询，并被要求在固定的数据结构上评估某些复杂的表达式。噢，算了吧……2026 年了，谁还想做那种事？Little Cyan Fish 想做点不一样的。他要求你自己发明数据结构。
你的任务是构造一棵有根二叉树 $T$：
- $T$ 的每个内部节点（internal vertex）* 都有且仅有两个子节点。
- $T$ 恰好有 $m$ 个叶子节点，标记为 $1$ 到 $m$。
图 1：一个 $m=6$ 的合法 $T$。每个内部节点都有两个子节点，叶子节点以某种顺序标记为 $1, \dots, m$。此处的深度为 $5$。
对于任意叶子标签集合 $S$，定义其在 $T$ 上的代价为 $T$ 中满足以下条件的内部节点 $v$ 的数量：$v$ 的子树同时包含：
- 至少一个标签属于 $S$ 的叶子。
- 至少一个标签不属于 $S$ 的叶子。
Little Cyan Fish 给了你两棵有根树 $T_1$ 和 $T_2$。两棵树的节点均标记为 $1$ 到 $n$，且节点 $1$ 是每棵树的根。他还给了你 $m$ 个有序对 $(x_i, y_i)$，其中 $x_i$ 是 $T_1$ 中的一个节点，$y_i$ 是 $T_2$ 中的一个节点。 $T$ 中标记为 $\ell$ 的叶子与值 $x_\ell$ 和 $y_\ell$ 相关联。
对于一棵有根树 $T$ 和一个节点 $x$，令 $\text{path}(T, x)$ 为从 $x$ 到 $T$ 的根的路径上的节点集合，包含两个端点。
Little Cyan Fish 希望你知道，对于 $T_1$ 的每个节点 $u$，定义 $Q_1(u) = \{\ell \mid x_\ell \in \text{path}(T_1, u)\}$。类似地，对于 $T_2$ 的每个节点 $u$，定义 $Q_2(u) = \{\ell \mid y_\ell \in \text{path}(T_2, u)\}$。每个 $Q_i(u)$ 都是 $T$ 的叶子标签集合。
* 叶子节点是没有子节点的节点，内部节点是除叶子节点以外的节点。
图 2：集合 $\text{path}(T_i, x)$ 包含从 $x$ 到根的唯一路径上的每个节点，包括两个端点。
Little Cyan Fish 检查的集合是所有 $1 \le u \le n$ 的 $Q_1(u)$ 和 $Q_2(u)$。如果你的数据结构满足以下两个要求，Little Cyan Fish 就会接受它：
- $T$ 中每个节点的深度最多为 $100$，其中根节点的深度为 $1$；
- 在所有 $2n$ 个被检查的集合中，最大代价最多为 $16\,666$。
向 Little Cyan Fish 展示你才是真正的数据结构大师！
输入格式
第一行包含两个整数 $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$ 是 $T_1$ 中节点 $i$ 的父节点。
下一行包含 $n - 1$ 个整数 $p'_2, p'_3, \dots, p'_n$ ($1 \le p'_i < i$)，描述树 $T_2$。整数 $p'_i$ 是 $T_2$ 中节点 $i$ 的父节点。
接下来的 $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
1
样例输入 2
3 3 1 1 1 2 1 1 2 2 3 3
样例输出 2
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
样例输出 3
0 0 1 0 0 3 8 0 2 7 0 4 0 5 6
说明
样例 1 的说明：该二叉树只有一个标记为 $1$ 的叶子。其深度为 $1$，且每个可能的查询代价均为 $0$。