Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. DFS

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputLet $$$T$$$ be a tree on $$$n$$$ vertices. Consider a graph $$$G_0$$$, initially equal to $$$T$$$. You are given a sequence of $$$q$$$ updates, where the $$$i$$$-th update is given as a pair of two distinct integers $$$u_i$$$ and $$$v_i$$$.

For every $$$i$$$ from $$$1$$$ to $$$q$$$, we define the graph $$$G_i$$$ as follows:

- If $$$G_{i-1}$$$ contains an edge $$$\{u_i, v_i\}$$$, then remove this edge to form $$$G_i$$$.
- Otherwise, add this edge to $$$G_{i-1}$$$ to form $$$G_i$$$.

Formally, $$$G_i := G_{i-1} \triangle \{\{u_i, v_i\}\}$$$ where $$$\triangle$$$ denotes the set symmetric difference.

Furthermore, it is guaranteed that $$$T$$$ is always a subgraph of $$$G_i$$$. In other words, an update never removes an edge of $$$T$$$.

Consider a connected graph $$$H$$$ and run a depth-first search on it. One can see that the tree edges (i.e. the edges leading to a not yet visited vertex at the time of traversal) form a spanning tree of the graph $$$H$$$. This spanning tree is not generally fixed for a particular graph — it depends on the starting vertex, and on the order in which the neighbors of each vertex are traversed.

We call vertex $$$w$$$ good if one can order the neighbors of each vertex in such a way that the depth-first search started from $$$w$$$ produces $$$T$$$ as the spanning tree. For every $$$i$$$ from $$$1$$$ to $$$q$$$, find and report the number of good vertices.

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.

Examples

Input

3 2

1 2

1 3

2 3

3 2

Output

2

3

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

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\}$$$.

- 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.

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\}$$$

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 02:47:42 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|