Cho một đồ thị cây có N đỉnh, mỗi đỉnh được đánh số từ 1 tới N, gốc của cây là đỉnh 1 và ban đầu các đỉnh đều có giá trị là 0. Cho 3 loại truy vấn sau:
1 x: Gán đỉnh x và các đỉnh thuộc cây con gốc x của nó giá trị 1.
2 x: Gán đỉnh x và các đỉnh tổ tiên của nó giá trị 0.
3 x: Xác định giá trị hiện tại của đỉnh X.
Input
Dòng 1: Số nguyên N, số lượng đỉnh của cây (1<=N<=10^5).
N dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v là một cạnh của đồ thị.
Dòng N+2: Số nguyên Q, số truy vấn (1<=Q<=10^5).
Q dòng tiếp theo là các truy vấn đưa ra.
Output
Kết quả ứng với truy vấn số 3