Cây nước

Cho một cây có gốc gồm $n$ đỉnh, đỉnh gốc là đỉnh số $1$. Mỗi đỉnh là một bể chứa, ban đầu tất cả các bể đều rỗng. Các cạnh của cây là các đường ống dẫn nước theo chiều từ cha xuống con.

Bạn cần xử lý $q$ thao tác trên cây, mỗi thao tác thuộc một trong ba loại sau:

1. Đổ nước vào đỉnh $v$: đỉnh $v$ và toàn bộ các đỉnh thuộc cây con gốc $v$ đều được lấp đầy nước.
2. Tháo cạn đỉnh $v$: đỉnh $v$ và tất cả tổ tiên của $v$ (đường đi từ $v$ lên gốc) đều bị tháo cạn nước.
3. Truy vấn đỉnh $v$: trả lời $1$ nếu hiện tại đỉnh $v$ đang chứa nước, ngược lại trả lời $0$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số đỉnh của cây.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số $a_i$, $b_i$ mô tả một cạnh của cây.
• Dòng tiếp theo chứa số nguyên $q$ — số thao tác.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số $c_i$, $v_i$ trong đó $c_i$ là loại thao tác và $v_i$ là đỉnh được thao tác.

Dữ liệu ra

Với mỗi thao tác loại $3$, in ra một dòng chứa $1$ nếu đỉnh đang chứa nước, $0$ nếu rỗng. Các câu trả lời in theo đúng thứ tự xuất hiện trong dữ liệu vào.

Ràng buộc

• $1\le n\le 500000$
• $1\le q\le 500000$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$
• $1\le c_i\le 3$, $1\le v_i\le n$
• Dữ liệu vào đảm bảo đồ thị cho là một cây.

Ví dụ