2720: T5 城市攻击
内存限制：128 MB
时间限制：1.500 S
评测方式：文本比较
命题人：
提交：7
解决：1
题目描述
小$W$ 是个野心家，想要去攻击一些城市。
我们不妨设城市是一个有 $n$ 个节点的树（$n-1$ 条边的连通无向图），小$W$ 打算对城市发起两次攻击，每次攻击针对城市上的一个节点，攻击后该节点以及与该节点相关联的边都会损坏。
小$W$ 有 $q$ 个攻击计划，你需要为每个攻击计划计算完成攻击后没有损坏的节点和边构成的图的连通块个数。
我们不妨设城市是一个有 $n$ 个节点的树（$n-1$ 条边的连通无向图），小$W$ 打算对城市发起两次攻击，每次攻击针对城市上的一个节点，攻击后该节点以及与该节点相关联的边都会损坏。
小$W$ 有 $q$ 个攻击计划，你需要为每个攻击计划计算完成攻击后没有损坏的节点和边构成的图的连通块个数。
输入
第一行两个正整数 $n,q$，表示树的节点个数和进攻计划总数。
接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上的一条边，再接下来 $q$ 行，每行两个整数 $x,y$，表示该进攻计划打算进攻的两个节点。
接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上的一条边，再接下来 $q$ 行，每行两个整数 $x,y$，表示该进攻计划打算进攻的两个节点。
输出
对于每个询问，输出一行一个非负整数表示答案。
样例输入 复制
3 3
1 2
2 3
1 2
2 3
1 3样例输出 复制
1
1
1提示
```input2
4 2
1 2
1 3
1 4
1 2
2 3
```
```output2
2
1
```
## 数据范围
对于全部数据 $1\le n,q\le2\times10^5$，$1\le u,v\le n$，$1\le x,y\le n$，保证输入的边构成一棵树。
| 测试点 | $n,q \leq$ | 特殊性质 |
| :--------: | :-----------: | :--------------------------------------: |
| $1\sim 2$ | $2000$ | 无 |
| $3\sim 5$ | $2\times10^5$ | $x=y$ |
| $6\sim 7$ | $2\times10^5$ | 树将构成一条链（所有节点度数不超过 $2$） |
| $8\sim 10$ | $2\times10^5$ | 无 |
4 2
1 2
1 3
1 4
1 2
2 3
```
```output2
2
1
```
## 数据范围
对于全部数据 $1\le n,q\le2\times10^5$，$1\le u,v\le n$，$1\le x,y\le n$，保证输入的边构成一棵树。
| 测试点 | $n,q \leq$ | 特殊性质 |
| :--------: | :-----------: | :--------------------------------------: |
| $1\sim 2$ | $2000$ | 无 |
| $3\sim 5$ | $2\times10^5$ | $x=y$ |
| $6\sim 7$ | $2\times10^5$ | 树将构成一条链（所有节点度数不超过 $2$） |
| $8\sim 10$ | $2\times10^5$ | 无 |