All Tracks Data Structures Advanced Data Structures Segment Trees Problem

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