题目描述

某天，$C$ 和 $K$ 觉得很无聊，于是决定玩一个经典小游戏：

在一棵有 $n$ 个结点的有根树上，标号为 $i$ 的节点上有 $a_i$ 个棋子。游戏时玩家轮流操作，每次可以将任意一个节点 $u$ 上的一个棋子放置到任意一个点 $v \in U(u)$ 上，其中 $U(u) = \text{subtree}\{u\} \setminus \{u\}$，表示 $u$ 的子树内（不包含 $x$ 本身）的点组成的集合。不能进行操作者失败。

而 $C$ 和 $K$ 作为 P** 和 T** 的在读学生，这种一眼就能找出必胜策略的游戏实在是索然无味，于是两人觉得，每个人给自己一个特殊能力可能会比较有趣：

• $C$ 在开始游戏之前，可以选择将当前树的树根 $R$ 换到与 $R$ 相邻的任意一个点 $R'$ 上。定义两个点相邻当且仅当这两个点有边直接相连。
• $K$ 在开始游戏之前，必须选择树上的一个节点，在上面加上一颗棋子。

$C$ 和 $K$ 决定玩 $m$ 局游戏。每局游戏的流程如下：

1. 游戏开始前，$C$ 和 $K$ 会商量好，先在标号为 $x$ 的节点上放上一个棋子，然后将树根设为 $y$。
2. 之后 $C$ 可以选择是否发动特殊能力，$C$ 决策完之后 $K$ 可以选择是否发动特殊能力。
3. 特殊能力的决策结束后，会在这棵树上进行一局 $C$ 先手、$K$ 后手的游戏。游戏完成后会将树上棋子的状态还原到流程 1 结束后的状态。

$C$ 觉得这个游戏可以出成一个简单题，于是他决定考考你：$C$ 在每局游戏的第二步的时候，有多少种决策方式使得不管 $K$ 如何进行特殊能力的操作，开始游戏时都存在必胜策略？两种决策方式不同，当且仅当两种决策更换的树根 $R'$ 不同，或者两者中仅有一个没有发动特殊能力。

---

输入格式

第一行包括一个整数，表示该测试点所在的子任务的分数。你可以使用这个信息判断该测试点满足的特殊性质。特别的，下发样例中此行使用 $0$ 代替。

第二行包含两个用空格隔开的正整数 $n$, $m$，表示树的节点数目以及游戏的轮数。树上的节点从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行，每行包含两个用空格隔开的正整数 $u_i$, $v_i$，满足 $1 \le u_i,v_i \le n$，表示编号为 $u_i$ 和 $v_i$ 的节点之间有边直接相连。

接下来一行包含 $n$ 个用空格隔开的整数 $a_1,a_2,\ldots,a_n$，满足 $0 \leq a_1,a_2,\ldots,a_n \leq 10^9$。

接下来 $m$ 行，每行包含两个用空格隔开的正整数 $x$, $y$ 描述一局游戏，满足 $1 \le x,y \le n$。

---

输出格式

你需要输出 $m$ 行，其中第 $i$ 行应当包含一个非负整数 $x$ 表示第 $i$ 局游戏中，$C$ 存在多少种使用特殊能力的决策方案，使得 $C$ 在这局游戏中存在必胜策略。注意，不使用特殊能力也是一种可能可行的决策方案。

---

样例 1

输入

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

输出

2
1

第一局游戏中，$C$ 存在两种胜利的方式：不使用特殊能力，或者将根节点换到一号点上。 第二局游戏中，$C$ 只有一种胜利的方式：将根节点换到二号点上。

---

样例 2

输入

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

输出

1
1
0
1
1
1
0
0
2
1

---

样例 3 见附加文件中的 3.in 与 3.ans。

样例 4 见附加文件中的 4.in 与 4.ans。

数据范围与提示

子任务分数	$1 \le n,m \le$	$\max\{a_1,a_2,\dots,a_n\} \le$	特殊性质
16	$5$	$1$	无
15	$300$
14	$5000$	$10^9$
13	$100000$		保证给出的树是一条链
12			保证给出的树存在一个点度数为 $n-1$
11			保证 $m$ 次游戏初始给定根一致
10	$500000$		无
9	$1000000$