Little Cyan Fish は University of Cup でデータ構造のマスタークラスを教えています。従来のデータ構造の問題では、一連のクエリが与えられ、固定されたデータ構造上で何らかの複雑な式を評価するように求められるのが一般的でした。しかし、2026 年にそんなことをしたい人がいるでしょうか？Little Cyan Fish は少し違ったことをしたいと考えています。彼はあなたに、データ構造を自分で発明するように求めています。

あなたの課題は、根付き二分木 $T$ を構築することです。

• $T$ のすべての内部頂点（internal vertex）は、ちょうど 2 つの子を持ちます。
• $T$ はちょうど $m$ 個の葉（leaf）を持ち、それぞれ $1$ から $m$ までのラベルが付けられています。

図 1: $m = 6$ の場合の有効な $T$。すべての内部頂点はちょうど 2 つの子を持ち、葉には $1, \dots, m$ のラベルが何らかの順序で付けられている。ここでの深さは 5 である。

葉のラベルの任意の集合 $S$ に対して、$T$ 上でのそのコストを、$T$ の内部頂点 $v$ のうち、その部分木が以下を両方含むようなものの数と定義します。

• ラベルが $S$ に属する葉が少なくとも 1 つ。
• ラベルが $S$ に属さない葉が少なくとも 1 つ。

Little Cyan Fish はあなたに 2 つの根付き木 $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)$ です。以下の 2 つの要件を満たす場合、Little Cyan Fish はあなたのデータ構造を受け入れます。

• $T$ のすべての頂点の深さは高々 100 である（根の深さは 1 とする）。
• チェックされるすべての $2n$ 個の集合において、最大コストは高々 16 666 である。

Little Cyan Fish にあなたが真のデータ構造のマスターであることを示してください！

入力

入力の最初の行には、2 つの整数 $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$ 番目には、2 つの整数 $x_i$ と $y_i$ ($1 \le x_i, y_i \le n$) が含まれます。

出力

構築した二分木 $T$ を記述する整数の列を 1 行で出力してください。

• ラベル $i$ の葉は整数 $i$ で記述されます。
• 内部頂点は整数 $0$ で記述され、その後に左部分木の記述、次に右部分木の記述が続きます。

このエンコーディングの下では、$1$ から $m$ までのすべての整数がちょうど 1 回ずつ現れ、$0$ の各出現は 1 つの内部頂点を表します。

例えば、列 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 つだけ持ちます。その深さは 1 であり、すべての可能なクエリのコストは 0 です。