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

範例 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$。