题目描述

训练师遥在一棵树形场地上安排追逐训练。场地有 $N$ 个顶点，边均为无向边。

每一轮训练中有两名角色：狮子负责追捕，斑马负责逃跑。轮开始时，斑马和狮子位于两个不同的顶点。狮子始终知道斑马的位置，并以每秒一条边的速度追赶它。

斑马不知道狮子的具体位置，但始终知道自己与狮子的距离。基于这个距离信息，斑马每秒可以选择下列两种行动之一：

• 花费 $1$ 秒移动到任意相邻顶点；
• 原地停留 $1$ 秒。

当斑马与狮子在某个顶点或某条边上相遇时，本轮结束。如果双方沿同一条边相向移动，那么它们会在开始移动后的 $0.5$ 秒相遇。

斑马会选择策略，使得在所有可能的狮子初始位置中，自己被抓住的最早时间尽可能晚。现在给出 $Q$ 轮询问。第 $i$ 轮中，斑马从顶点 $v_i$ 出发，并且它与狮子的初始距离为 $d_i$。你需要求出双方都按最优策略行动时，这一轮结束的最小时间。

输入格式

第一行包含两个整数 $N,Q$，表示树的顶点数和询问轮数。

接下来 $N-1$ 行，每行包含两个整数 $a_i,b_i$，表示顶点 $a_i$ 和 $b_i$ 之间有一条边。输入保证给出的图是一棵树。

接下来 $Q$ 行，每行包含两个整数 $v_j,d_j$，表示一轮中斑马的起点，以及斑马与狮子的初始距离。

输入保证至少存在一个顶点 $w_j$，使得 $v_j$ 与 $w_j$ 的距离恰好为 $d_j$。

输出格式

对于每个询问，输出一行一个整数，表示双方都按最优策略行动时，该轮结束的最小时间。

数据范围

• $2\le N\le 10^5$；
• $1\le Q\le 10^5$；
• $1\le v_j\le N$；
• $1\le d_j\le N-1$。

样例 1

输入

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

输出

4
1

解释

第一轮中，斑马在顶点 $1$，与狮子的距离为 $4$，因此狮子只能在顶点 $5$。最优策略是斑马尽可能久地停在顶点 $1$，答案为 $4$。

第二轮中，斑马在顶点 $3$，与狮子的距离为 $1$，狮子可能在顶点 $2$ 或顶点 $4$。如果斑马向其中一侧移动，最坏情况下会在 $0.5$ 秒后于边上相遇；如果斑马原地不动，则无论狮子在哪一侧，都会在 $1$ 秒后相遇。因此答案为 $1$。

样例 2

输入

11 2
1 2
2 3
1 4
4 5
1 6
6 7
7 8
1 9
9 10
10 11
3 2
10 4

输出

2
5