A tree is a simple graph in which every two vertices are connected by exactly one path. You are given a rooted tree with \(n\) vertices and a lamp is placed on each vertex of the tree.
You are given \(q\) queries of the following two types:
Note: Initially, all the lamps are turned On and the tree is rooted from vertex number \(1\).
Input format
Note: It is guaranteed that these edges form a tree rooted from vertex \(1\).
Output format
For every query of type 2, print the answer in a single line.
Constraints
\(1 \leq n, q \leq 5 \times 10^{5}\\ 1 \leq a_i, b_i \leq n\\ 1 \leq t_i \leq 2\\ 1 \leq v_i \leq n\)
Obviously the answer now for vertex $$2$$ is $$1$$