Problem Description

小Q认为，偶数具有对称美，而奇数则没有。

给定一棵$n$个点的树，任意两点之间有且仅有一条直接或间接路径。这些点编号依次为$1$到$n$，其中编号为$i$的点上有一个正整数$a_i$。

定义集合$S(u,v)$为$u$点到$v$点的唯一最短路径上经过的所有点$x$(包括$u$和$v$)对应的正整数$a_x$的集合。小Q将在$m$个$S(u,v)$中寻找最小的对称数。因为偶数具有对称美，所以对称数是指那些出现了偶数次(包括$0$次)的正整数。

请写一个程序，帮助小Q找到最小的对称数。

Input

第一行包含一个正整数$T(1\leq T\leq 10)$，表示测试数据的组数。

每组数据第一行包含两个正整数$n,m(1\leq n,m\leq 200000)$，分别表示点数和询问数。

第二行包含$n$个正整数$a_1,a_2,...,a_n(1\leq a_i\leq 200000)$，依次表示每个点上的数字。

接下来$n-1$行，每行两个正整数$u_i,v_i(1\leq u_i,v_i\leq n,u_i\neq v_i)$，表示一条连接$u_i$和$v_i$的双向树边。

接下来$m$行，每行两个正整数$u_i,v_i(1\leq u_i,v_i\leq n)$，依次表示每个询问。

Output

对于每个询问输出一行一个正整数，即最小的对称数。

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

2
1
1