The KOI laboratory is conducting research using a particle accelerator. The particle accelerator at the KOI laboratory consists of $N$ rooms and $N - 1$ bidirectional passages connecting them, such that any two distinct rooms can be reached from each other using only the passages. In other words, the particle accelerator forms a tree structure.

The rooms in the particle accelerator are labeled with distinct numbers from $0$ to $N - 1$, and the passages are labeled with distinct numbers from $0$ to $N - 2$. For every $0 \le i \le N - 2$, the $i$-th passage connects room $A[i]$ and room $B[i]$.

Recently, the KOI laboratory has been conducting IOI particle collision experiments. Since generating an IOI particle is very difficult, one can attempt to generate at most one particle in each room of the particle accelerator. If the generation of an IOI particle in a room is successful, one IOI particle will exist in that room in a stationary state. Conversely, if the generation fails, that room is closed for equipment inspection and can no longer be used.

The KOI laboratory intends to conduct experiments after selecting several rooms to attempt IOI particle generation. The experiment consists of a sequence of collision experiments, where in each collision experiment, two rooms containing IOI particles are selected to perform an IOI particle collision experiment. At this time, there must be no rooms containing IOI particles on the path connecting the selected rooms, and there must be no rooms where IOI particle generation failed. After an IOI particle collision experiment is performed, the two particles used in the collision experiment are annihilated. Note that for a room where IOI particle generation was successful but the IOI particle no longer exists, it may exist on the path connecting the two rooms selected in subsequent collision experiments.

You must determine the maximum number of collision experiments the KOI laboratory can perform. Initially, there are no IOI particles in any room of the particle accelerator, and IOI particle generation can be attempted for all rooms. The KOI laboratory attempts to generate IOI particles a total of $Q$ times, and for each generation attempt, you must determine the maximum number of collision experiments that can be performed in the current state.

Implementation Details

You must implement the following functions:

void initialize(int N, std::vector<int> A, std::vector<int> B)

• $N$: The number of rooms in the particle accelerator.
• $A, B$: Integer arrays of size $N - 1$. For every integer $0 \le i \le N - 2$, there exists a passage connecting room $A[i]$ and room $B[i]$.
• This function is called exactly once at the beginning.

int generate(int v, bool result)

• This function represents an attempt to generate an IOI particle in room $v$.
• This function is called a total of $Q$ times after the initialize function is called.
• $v$: The number of the room where IOI particle generation was attempted. It is guaranteed that IOI particle generation was not attempted in room $v$ before this function was called.
• $result$: Whether the IOI particle generation was successful. If the value is true, it means the IOI particle generation was successful, and an IOI particle now exists in room $v$. If the value is false, it means the IOI particle generation failed, and room $v$ is closed and can no longer be used.
• This function must return the maximum number of collision experiments that can be performed in the current state.

Constraints

• $2 \le Q \le N \le 200\,000$
• The particle accelerator of the KOI laboratory forms a tree structure.
• $0 \le A[i], B[i] \le N - 1$ and $A[i] \neq B[i]$ for all $0 \le i \le N - 2$.
• $0 \le v \le N - 1$ for all generate function calls; all $v$ are distinct.

Subtasks

1. (9 points) $2 \le Q \le N \le 5\,000$
2. (16 points) $A[i] = i$ and $B[i] = i + 1$ for all $0 \le i \le N - 2$.
3. (20 points) There are at most 20 calls to the generate function where $result = \text{false}$.
4. (23 points) There are at most 20 calls to the generate function where $result = \text{true}$.
5. (32 points) No additional constraints.

Examples

Input 1

6 5
0 1
0 2
0 3
3 4
3 5
1 1
5 1
0 0
4 1
3 1

Output 1

0
1
0
1
1

Note

The structure of the particle accelerator is as follows:

When room 1 is successful:

When room 5 is successful:

When room 0 fails:

When room 4 is successful:

When room 3 is successful:

After the collision between room 3 and room 5:

Sample Grader

The sample grader receives input in the following format:

• Line 1: $N$ $Q$
• Line $2 + i$ ($0 \le i \le N - 2$): $A[i]$ $B[i]$
• Line $N + 1 + j$ ($0 \le j \le Q - 1$): $v$ $result$ (input 1 if $result$ is true, 0 if false)

The sample grader outputs the following:

• Line $1 + j$ ($0 \le j \le Q - 1$): The value returned by the $j$-th generate function call.

Note that the sample grader may differ from the grader used in actual grading.