SOLVE

LATER

Tree query

/

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:

- \(1\ v\): You switch the lamp placed on the vertex \(v\), that is, either from
**On**to**Off**or**Off**to**On**. - \(2\ v\): Determine the number of vertices connected to the subtree of \(v\) if you only consider the lamps that are in
**On**state. In other words, determine the number of vertices in the subtree of \(v\), such as \(u\), that can reach from \(v\) by using only the vertices that have lamps in the**On**state.

**Note**: Initially, all the lamps are turned **On** and the tree is rooted from vertex number \(1\).

**Input format**

- First line: Two integers \(n\) and \(q\) denoting the number of vertices and queries
- Next \(n -1\) lines: Two number \(a_i\) and \(b_i\) denoting an edge between the vertices \(a_i\) and \(b_i\)
- Next \(q\) lines: Two integers \(t_i\) and \(v_i\), where \(t_i\) is the type of the \(i^{th}\) query

**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\)

Explanation

Obviously the answer now for vertex $$2$$ is $$1$$

Time Limit:
4.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...