Given a rooted tree with $n$ nodes, labeled $1$ to $n$, where node $1$ is the root. Xiao Ming has a set of nodes $S$. For any node $u \in S$, he defines $w_u$ as the number of nodes in the subtree of $u$ (including $u$ itself) that are contained in the set $S$. For convenience, for any node not in $S$, we define $w_u = 0$.
Xiao Ming wants you to choose a connected component $C$ that contains the root. Let $a$ be the number of nodes in $C$ that are also in $S$, and let $b$ be the maximum $w$ value among all nodes not in $C$. If there are no nodes outside $C$, then $b = 0$. Xiao Ming wants you to minimize $\max(a, b)$.
Xiao Ming thinks this problem is relatively simple, so he provides $q$ operations. Each operation adds a node to or removes a node from $S$. Please provide the minimum value of $\max(a, b)$ after each operation.
Input
The first line contains a positive integer $n$, the number of nodes.
The next $n-1$ lines each contain two integers $x, y$, representing an edge $(x, y)$ in the tree.
The next line contains a positive integer $q$, the number of operations.
The next $q$ lines each contain two integers $t, v$, representing an operation. If $t = 1$, the operation is to add node $v$ to $S$; it is guaranteed that $v \notin S$ before the operation. If $t = 2$, the operation is to remove node $v$ from $S$; it is guaranteed that $v \in S$ before the operation. Initially, $S$ is an empty set.
Output
After each operation, output a single integer on a new line representing the answer.
Examples
Input 1
5
1 2
1 3
1 4
2 5
5
1 4
1 1
1 2
1 5
2 2Output 1
1
1
1
2
1Note 1
After the first operation, $S = \{4\}$. A possible choice is $C = \{1\}$, where $a = 0, b = 1$.
After the second operation, $S = \{1, 4\}$. A possible choice is $C = \{1\}$, where $a = 1, b = 1$.
After the third operation, $S = \{1, 2, 4\}$. A possible choice is $C = \{1\}$, where $a = 1, b = 1$.
After the fourth operation, $S = \{1, 2, 4, 5\}$. A possible choice is $C = \{1, 2\}$, where $a = 2, b = 1$.
After the fifth operation, $S = \{1, 4, 5\}$. A possible choice is $C = \{1\}$, where $a = 1, b = 1$.
Example 2
See tree2.in and tree2.ans in the additional files.
Example 3
See tree3.in and tree3.ans in the additional files.
Subtasks
For all test cases: $1 \le n \le 5 \times 10^5$, $1 \le q \le 10^6$, $1 \le x, y, v \le n$, $t \in \{1, 2\}$.
| Test Case ID | $n \le$ | $q \le$ | Special Constraints |
|---|---|---|---|
| $1 \sim 2$ | $100$ | $500$ | None |
| $3 \sim 4$ | $2 \times 10^4$ | $2 \times 10^4$ | None |
| $5 \sim 6$ | $10^5$ | $2 \times 10^5$ | A |
| $7 \sim 8$ | $2 \times 10^5$ | $4 \times 10^5$ | B |
| $9 \sim 11$ | C | ||
| $12 \sim 16$ | None | ||
| $17 \sim 20$ | $5 \times 10^5$ | $10^6$ | None |
The meanings of the special constraints in the table are:
A: The size of set $S$ never exceeds $50$ at any time.
B: The tree is a chain, and the degree of node $1$ is $1$.
C: The parent of each node has a smaller index than the node itself, $n = q$, and the $i$-th operation adds node $i$ to $S$.