在回答出恐怖岛第一个问题后，膜法师 lanpang 给你出了第二道考题，回答正确你就可以成为一名合格的膜法师了。

这一题，膜法师 lanpang 将告诉你恐怖岛真正的地图，你将挑战一个真正的反恐之旅！

首先你将知道恐怖岛的节点数 $n$ 和全部 $n-1$ 条无向链接，保证给出的地图是合法的连通图。

但与理想状态不同的是，一些恐怖恶魔属于同种类，一旦你杀死一只恐怖恶魔，其它同种族的恐怖恶魔将打开防御措施直到你杀死下一只恐怖恶魔，恐怖恶魔开启防御措施时你将无法杀死他。

也就是说，你在杀死一名恐怖恶魔后，在下一次无法杀死和它同一种类的恐怖恶魔，但如果你下一次杀死的是另一种类恐怖恶魔，之后就又可以杀死与第一次同种类的恐怖恶魔。

而你现在需要回答 $q$ 次膜法师 lanpang 的提问，从一个起点，沿最短路到达终点（起点和终点可以相同），你将尽可能多地杀死这条路径中节点上的恐怖恶魔，那么你最多能杀死多少恐怖恶魔呢？

第一行为一个整数 $T(1\le T\le 20)$，代表有 $T$ 组样例。

对于每组样例：

输入第一行为两个整数 $n,q(1\le n,q\le 20000)$，代表恐怖岛有 $n$ 个节点，且膜法师 lanpang 有 $q$ 次询问。

接下来输入 $n-1$ 行，每行两个整数 $x$ 和 $y$ $(1\le x,y\le n\ ,x \ne y)$，代表节点 $x$ 和节点 $y$ 有一条无向边。

接下来一行有 $n$ 个整数 $a_1,a_2,\dots ,a_n(1\le a_i\le n)$，代表节点 $i$ 上的恐怖恶魔是第 $a_i$ 种。

最后输入 $q$ 行，每行两个整数 $u$ 和 $v$ $(1\le u,v\le n)$，代表这一次询问的起点为 $u$ 终点为 $v$。

对于每组样例：

输出 $q$ 行，每行一个数字，表示这一次询问你最多可以杀死多少恐怖恶魔。

样例中树的结构是 $1-2-3-4$，节点的种类是 $1-2-2-1$。

四次询问的最优击杀顺序分别是 $(1)$，$(1-2)$，$(1-2)$，$(1-2-4)$。