DFS

Description:

Input:

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \le n \le 2\cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the number of nodes and the number of updates, respectively.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — vertices connected by an edge in $$$T$$$. It is guaranteed that this graph is a tree.

Each of the next $$$q$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — the endpoints of the edge that is added or removed. It is guaranteed that this edge does not belong to $$$T$$$.

Output:

For each update, print one integer $$$k$$$ — the number of good vertices $$$w$$$ after the corresponding update.

Sample Input:

3 2
1 2
1 3
2 3
3 2

Sample Output:

2
3

Sample Input:

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

Sample Output:

3
2
3
2
3
2

Note:

The first sample is depicted in the following figure.

After the first update, $$$G$$$ contains all three possible edges. The result of a DFS is as follows:

• Let the starting vertex be $$$1$$$. We have two choices of ordering the neighbors of $$$1$$$, either $$$[2, 3]$$$ or $$$[3, 2]$$$.
  • If we choose the former, then we reach vertex $$$2$$$. Regardless of the ordering of its neighbors, the next visited vertex will be $$$3$$$. Thus, the spanning tree generated by this DFS will contain edges $$$\{1, 2\}$$$ and $$$\{2, 3\}$$$, which does not equal to $$$T$$$.
  • If we choose the latter, we obtain a spanning tree with edges $$$\{1, 3\}$$$ and $$$\{2, 3\}$$$.
  Hence, there is no way of ordering the neighbors of vertices such that the DFS produces $$$T$$$, and subsequently $$$1$$$ is not a good vertex.
• Let the starting vertex be $$$2$$$. We have two choices of traversing its neighbors. If we visit $$$3$$$ first, then the spanning tree will consist of edges $$$\{2,3\}$$$ and $$$\{1,3\}$$$, which is not equal to $$$T$$$. If we, however, visit $$$1$$$ first, then we can only continue to $$$3$$$ from here, and the spanning tree will consist of edges $$$\{1, 2\}$$$ and $$$\{1,3\}$$$, which equals to $$$T$$$. Hence, $$$2$$$ is a good vertex.
• The case when we start in the vertex $$$3$$$ is symmetrical to starting in $$$2$$$, and hence $$$3$$$ is a good vertex.

Therefore, the answer is $$$2$$$.

After the second update, the edge between $$$2$$$ and $$$3$$$ is removed, and $$$G = T$$$. It follows that the spanning tree generated by DFS will be always equal to $$$T$$$ independent of the choice of the starting vertex. Thus, the answer is $$$3$$$.

In the second sample, the set of good vertices after the corresponding query is:

• $$$\{2, 3, 5\}$$$
• $$$\{3, 5\}$$$
• $$$\{3, 4, 5\}$$$
• $$$\{4, 5\}$$$
• $$$\{4, 5, 6\}$$$
• $$$\{5, 6\}$$$