T5 城市攻击

时间：$1s$

空间：$256M$

题目描述

小$W$ 是个野心家，想要去攻击一些城市。

我们不妨设城市是一个有 $n$ 个节点的树（$n-1$ 条边的连通无向图），小$W$ 打算对城市发起两次攻击，每次攻击针对城市上的一个节点，攻击后该节点以及与该节点相关联的边都会损坏。

小$W$ 有 $q$ 个攻击计划，你需要为每个攻击计划计算完成攻击后没有损坏的节点和边构成的图的连通块个数。

输入格式

第一行两个正整数 $n,q$，表示树的节点个数和进攻计划总数。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上的一条边，再接下来 $q$ 行，每行两个整数 $x,y$，表示该进攻计划打算进攻的两个节点。

输出格式

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

样例

input1

3 3
1 2
2 3
1 2
2 3
1 3

output1

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$，保证输入的边构成一棵树。