Little Cyan Fish đang giảng dạy Lớp học Bậc thầy về Cấu trúc Dữ liệu tại Đại học Cup. Trong các bài toán cấu trúc dữ liệu truyền thống, bạn thường sẽ nhận được một loạt các truy vấn và được yêu cầu đánh giá một biểu thức phức tạp trên một cấu trúc dữ liệu cố định. Ồ, thôi nào... ai lại muốn làm điều đó vào năm 2026 chứ? Little Cyan Fish muốn làm một điều gì đó khác biệt. Anh ấy yêu cầu bạn tự mình phát minh ra cấu trúc dữ liệu.

Nhiệm vụ của bạn là xây dựng một cây nhị phân có gốc $T$:

• Mỗi đỉnh trong* của $T$ có đúng hai con.
• $T$ có đúng $m$ lá, được đánh nhãn từ $1$ đến $m$.

Hình 1: Một cây $T$ hợp lệ cho $m = 6$. Mỗi đỉnh trong có đúng hai con, và các lá mang nhãn $1, \dots, m$ theo một thứ tự nào đó. Ở đây độ sâu là 5.

Với bất kỳ tập hợp $S$ các nhãn lá nào, định nghĩa chi phí của nó trên $T$ là số lượng các đỉnh trong $v$ của $T$ sao cho cây con của $v$ chứa cả:

• Ít nhất một lá có nhãn thuộc $S$.
• Ít nhất một lá có nhãn không thuộc $S$.

Little Cyan Fish đưa cho bạn hai cây có gốc $T_1$ và $T_2$. Cả hai cây đều có các đỉnh được đánh nhãn từ $1$ đến $n$, và đỉnh $1$ là gốc của mỗi cây. Anh ấy cũng đưa cho bạn $m$ cặp có thứ tự $(x_i, y_i)$, trong đó $x_i$ là một đỉnh của $T_1$ và $y_i$ là một đỉnh của $T_2$. Lá được đánh nhãn $\ell$ trong $T$ được liên kết với các giá trị $x_\ell$ và $y_\ell$.

Đối với một cây có gốc $T$ và một đỉnh $x$, gọi $path(T, x)$ là tập hợp các đỉnh trên đường đi từ $x$ đến gốc của $T$, bao gồm cả hai đầu mút.

Little Cyan Fish muốn bạn biết rằng, với mỗi đỉnh $u$ của $T_1$, định nghĩa $Q_1(u) = \{\ell \mid x_\ell \in path(T_1, u)\}$. Tương tự, với mỗi đỉnh $u$ của $T_2$, định nghĩa $Q_2(u) = \{\ell \mid y_\ell \in path(T_2, u)\}$. Mỗi $Q_i(u)$ là một tập hợp các nhãn lá của $T$.

*Một lá là một đỉnh không có con, và một đỉnh trong là một đỉnh không phải là lá.

Hình 2: Tập hợp $path(T_i, x)$ chứa mọi đỉnh trên đường đi duy nhất từ $x$ lên gốc, bao gồm cả hai đầu mút.

Các tập hợp mà Little Cyan Fish kiểm tra là $Q_1(u)$ và $Q_2(u)$ với mọi $1 \le u \le n$. Little Cyan Fish chấp nhận cấu trúc dữ liệu của bạn nếu nó thỏa mãn cả hai yêu cầu:

• Độ sâu của mọi đỉnh trong $T$ tối đa là $100$, trong đó gốc có độ sâu $1$;
• Trong số tất cả $2n$ tập hợp được kiểm tra, chi phí tối đa tối đa là $16\,666$.

Hãy cho Little Cyan Fish thấy bạn là bậc thầy thực sự về cấu trúc dữ liệu!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $m$ ($1 \le n, m \le 10^6$).

Dòng tiếp theo của dữ liệu vào chứa $n - 1$ số nguyên $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), mô tả cây $T_1$. Số nguyên $p_i$ là cha của đỉnh $i$ trong $T_1$.

Dòng tiếp theo của dữ liệu vào chứa $n - 1$ số nguyên $p'_2, p'_3, \dots, p'_n$ ($1 \le p'_i < i$), mô tả cây $T_2$. Số nguyên $p'_i$ là cha của đỉnh $i$ trong $T_2$.

$m$ dòng tiếp theo mô tả các cặp có thứ tự. Dòng thứ $i$ trong số này chứa hai số nguyên $x_i$ và $y_i$ ($1 \le x_i, y_i \le n$).

Dữ liệu ra

Xuất ra một dòng duy nhất chứa một dãy các số nguyên mô tả cây nhị phân $T$ mà bạn xây dựng.

• Một lá được đánh nhãn $i$ được mô tả bởi số nguyên $i$.
• Một đỉnh trong được mô tả bởi số nguyên $0$, theo sau là mô tả của cây con bên trái, sau đó là mô tả của cây con bên phải.

Theo cách mã hóa này, mọi số nguyên từ $1$ đến $m$ phải xuất hiện đúng một lần, và mỗi lần xuất hiện của $0$ đại diện cho một đỉnh trong.

Ví dụ, dãy $0\ 1\ 0\ 2\ 3$ mô tả một cây có gốc với lá $1$ là con bên trái và một đỉnh trong là con bên phải; đỉnh trong đó có các lá $2$ và $3$ là các con của nó.

Ví dụ

Ví dụ 1

1 1
1 1

1

Ví dụ 2

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

0 1 0 2 3

Ví dụ 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

Ghi chú

Giải thích Ví dụ 1: Cây nhị phân có một lá duy nhất được đánh nhãn $1$. Độ sâu của nó là $1$, và mọi truy vấn có thể có đều có chi phí $0$.