问题描述

这天, 小明在机房学习。

他发现机房里一共有 $n$ 台电脑, 编号为 1 到 $n$, 电脑和电脑之间有网线连接, 一共有 $n-1$ 根网线将 $n$ 台电脑连接起来使得任意两台电脑都直接或者间 接地相连。

小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和 多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑 用网线直接连接了另外 $d$ 台电脑, 那么任何经过这台电脑的信息都会延迟 $d$ 单 位时间 (发送方和接收方也会产生这样的延迟, 当然如果发送方和接收方都是 同一台电脑就只会产生一次延迟)。

小明一共产生了 $m$ 个疑问: 如果电脑 $u_i$ 向电脑 $v_i$ 发送信息, 那么信息从 $u_i$ 传到 $v_i$ 的最短时间是多少?

输入格式

输入共 $n+m$ 行, 第一行为两个正整数 $n, m$。

后面 $n-1$ 行, 每行两个正整数 $x, y$ 表示编号为 $x$ 和 $y$ 的两台电脑用网线 直接相连。

后面 $m$ 行, 每行两个正整数 $u_i, v_i$ 表示小明的第 $i$ 个疑问。

输出格式

输出共 $m$ 行, 第 $i$ 行一个正整数表示小明第 $i$ 个疑问的答案。

4 3
1 2
1 3
2 4
2 3
3 4
3 3

5
6
1

样例说明

这四台电脑各自的延迟分别为 2,2,1,1。

对于第一个询问, 从 2 到 3 需要经过 2,1,3, 所以时间和为 2+2+1=5。

对于第二个询问, 从 3 到 4 需要经过 3,1,2,4, 所以时间和为 1+2+2+1=6。

对于第三个询问, 从 3 到 3 只会产生一次延迟, 所以时间为 1 。

评测用例规模与约定

对于 30% 的数据, 保证 $n, m \leq 1000$;

对于 100% 的数据, 保证 $n, m \leq 100000$ 。