题目描述

Ted 和 Barney 已经厌倦了在 “MacLaren’s” 酒吧追女孩。现在，他们在一个由一棵树和两枚棋子组成的游戏里找到了更有趣的事情做。

游戏给定一棵有 $N$ 个顶点的树（即一个无环连通图），以及两枚分别放在两个不同顶点上的棋子：Ted 的棋子在顶点 $a$，Barney 的棋子在顶点 $b$。

他们的目标是把两枚棋子都移出这棵树。为此，树中的某些顶点被称为“出口”顶点。允许进行的移动如下：

• Ted 单独移动自己的棋子到相邻顶点。形式化地说，位于顶点 $a$ 的棋子可以移动到某个顶点 $a'$，满足树中存在边 $a-a'$。

• Barney 单独移动自己的棋子到相邻顶点。形式化地说，位于顶点 $b$ 的棋子可以移动到某个顶点 $b'$，满足树中存在边 $b-b'$。

• 两人同时移动各自的棋子，但要求两枚棋子之间的距离不能减少。形式化地说，若两枚棋子当前分别位于顶点 $a,b$，则可同时移动到顶点 $a',b'$，满足树中存在边 $a-a'$ 和 $b-b'$，且

  $$dist(a,b) \le dist(a',b').$$

  这里 $dist(x,y)$ 表示树上从 $x$ 到 $y$ 的简单路径经过的边数。

注意，在游戏的某个时刻，两枚棋子可以位于同一个顶点上；同样，两枚棋子也可以从同一个“出口”顶点离开树。

最终目标是在最少的移动次数内，将两枚棋子都移动到“出口”顶点。

Ted 和 Barney 觉得，如果只玩一次，这个游戏并不算太有趣。于是 Rado 建议他们对同一棵树回答 $Q$ 组不同的初始位置。

请编写程序 pawns，在同一棵树上回答这 $Q$ 次游戏：每次给出新的棋子初始顶点 $(a,b)$。

输入格式

第一行输入两个整数 $N,Q$，分别表示树的顶点数和询问数。
第二行输入一个长度为 $N$ 的序列 $e_1,e_2,\ldots,e_N$。若 $e_i=1$，则顶点 $i$ 是“出口”顶点；若 $e_i=0$，则顶点 $i$ 不是“出口”顶点。
接下来 $N-1$ 行，每行输入两个整数 $(u_i,v_i)$，表示树的一条边。
接下来 $Q$ 行，每行输入两个整数 $(a_i,b_i)$，表示第 $i$ 次询问中两枚棋子的初始位置。

输出格式

输出 $Q$ 行。第 $i$ 行输出一个整数 $x_i$，表示第 $i$ 次询问中，将位于顶点 $a_i,b_i$ 的两枚棋子移动到“出口”顶点所需的最少移动次数。

数据范围

• $1 \le N,Q \le 5 \times 10^5$
• 对每个 $1 \le i \le N-1$，都有 $1 \le u_i,v_i \le N$ 且 $u_i \ne v_i$
• 对每个询问，均有 $1 \le a_i,b_i \le N$ 且 $a_i \ne b_i$
• 保证至少存在一个 $i$ 使得 $e_i=1$

子任务

只有当某个子任务中的所有测试点全部通过时，才能获得该子任务的分数。

样例

输入

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

输出

4
1
2

样例解释

原题样例中的树如图所示。

对于第一组询问：前两步只能移动起始时位于顶点 $10$ 的那枚棋子。在这两步之前，不可能同时移动两枚棋子，否则它们之间的距离会缩短，这是不允许的。
对于第二组询问：顶点 $4$ 本身就是一个“出口”，因此这枚棋子无需移动。