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