Minimum Removals to Change Real Component Candidate

In 26's mind, there are \(n\) tasks forming a tree. Each task is either in a real or delusional state. Initially every task is delusional. The tree is rooted at task 1, and the depth of a task is defined as the number of tasks on the simple path from task 1 to that task (including both endpoints).

A set \(S\) of tasks is called a real connected component if for any two tasks that are real, the simple path between them on the tree (including endpoints) is entirely contained in \(S\). Among all such subsets, one with the minimum number of tasks is called a minimal real connected component. In each minimal real connected component, we define the candidate as the task with the smallest depth in that component.

Over time, some tasks change their state. There are a total of \(m\) operations. Each operation is one of the following two types:

1. Real u: Task \(u\) becomes real.
2. Want u: Task \(u\) becomes delusional.

After each operation, 26 asks: "How many extra tasks need to be switched to delusional in order to either change the position (i.e. the identity) of the candidate (the task with the smallest depth) in the minimal real connected component, or have no real tasks at all?"

Note: You are allowed to choose any subset of tasks that are currently real and flip them to delusional. In an optimal strategy, you may achieve the goal by simply switching the candidate task. Hence, if there is at least one real task, one extra switch is always enough. If no task is real then nothing needs to be done.

Your task is to process the operations in order and, after each one, output the minimum number of additional switches needed. (If there are no real tasks, output \(0\). Otherwise, output \(1\).)

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le 10^5)\) --- the number of tasks and the number of operations, respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing an edge in the tree between tasks \(u\) and \(v\). Task 1 is the root of the tree.

The following \(m\) lines each contain an operation in one of the following forms:

• Real u
• Want u

It is guaranteed that the operations result in a change of state for task \(u\) (i.e. no redundant state changes occur).

outputFormat

After each operation, output one integer on a new line: the minimum number of additional tasks that need to be switched to delusional (from real) so that either the candidate (the task with the smallest depth in the minimal real connected component) changes, or there are no real tasks.

Note: As explained in the description, if there is at least one real task the answer is always 1; otherwise, the answer is 0.

sample

3 4
1 2
1 3
Real 2
Real 3
Want 2
Want 3

1
1
1
0

</p>