Background

Sitting on a fast-moving train and looking at the yellowing leaves outside the window, Xiao Ka thought, “Another winter.” This is a season when everything withers. When a cold wind blows, the leaves turn yellow; when another cold wind blows, the ground becomes covered in gold.

Out of boredom, Xiao Ka discovered that leaves turn yellow following a pattern: on every tree, only the lower half is yellow, and the upper part is all green. Xiao Ka wondered how to count the number of yellow leaves.

Problem Description

You are given a rooted tree with $n(1\le n\le 10^5)$ nodes. The root is node $1$, and the depth of the root is $1$. Initially, all nodes in the entire tree are green.

Xiao Ka has $m(1\le m \le 10^5)$ operations.

Operation 1: Recolor the whole tree to green, then make all nodes with depth $\ge x$ turn yellow.

Operation 2: Query how many yellow nodes are in the subtree of a node $x$.

Input Format

The first line contains two positive integers $n,m$, denoting the number of nodes in the tree and the number of operations.

The next $n-1$ lines each contain two positive integers $x,y$, denoting an edge in the tree.

The next $m$ lines each contain two positive integers $op,x(1\le x\le n)$. If $op=1$, it means Operation 1; otherwise, it means Operation 2.

Output Format

For each Operation 2, output one line with one positive integer, denoting the number of yellow nodes in the subtree of $x$.

5 9
1 2
1 3
2 4
4 5
1 3
2 5
2 2
2 1
1 2
2 1
2 4
2 5
2 2

1
2
2
4
2
1
3

Hint

The tree in Sample 1 is as follows:

In the first coloring, nodes $4$ and $5$ are colored yellow. Querying the subtrees of nodes $5,2,1$, the answers are $1,2,2$, respectively.

In the second coloring, nodes $2,3,4,5$ are colored yellow. Querying the subtrees of nodes $1,4,5,2$, the answers are $4,2,1,3$, respectively.

Translated by ChatGPT 5