A 简单数据结构

时间限制: 4s
内存限制: 1024 MB

题目描述

给定一棵 $n$ 个点的树。 $m$ 次询问一条边 $(x, y)$，在树上加入这条边上得到一个唯一的环。问把环上的点和与其相连的边删掉之后得到的连通块个数。

每个询问独立。即不会真的加边以及删环。注意如果询问的边在树上本来就存在，视作二元环（即只删掉这两个点）。

输入格式

第一行两个正整数 $n, m$。

后 $n-1$ 行每行两个正整数 $u_i, v_i$ 表示一条树边。

后 $q$ 行每行两个正整数 $x, y$ 表示一次询问。

输出格式

对于每个询问，输出一行一个非负整数表示答案。

输入输出样例

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

3
4
2
2

样例解释

对于第一个询问，形成的环是 $(3,1,2,5)$，删去之后剩下三个连通块：\[4\],\{6\},\{7\}。

对于第二个询问，形成重边 $(2,5)$，删去之后剩下四个连通块：$\{1,3\},\{4\},\{6\},\{7\}$。

数据范围

对于 $100\%$ 的数据，$2 \le n \le 3 \times 10^5$，$1 \le m \le 3 \times 10^5$。保证输入的是树。保证询问中 $1 \le x,y \le n$。