时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗大学的第三十九届算法考试就要开始了，小 C 正在紧张地造题……

题目描述

小 C 想到了这样一个题目：给定一棵 $n$ 个结点的树，要求选手给每个结点分配一个权值，使得树上所有点的权值构成一个 $0$ 到 $n-1$ 的排列，并满足 $m$ 条限制，每条限制形如 $(x,y,v)$，表示树上从 $x$ 到 $y$ 路径上所有点的权值构成集合的 $\text{mex}$ 值等于 $v$。

小 C 已经想到了绝妙的正解做法，现在他需要你帮他写 SPJ 的核心部分。具体而言，你会接收到一棵 $n$ 个结点的树，其中编号为 $i$ 的点有权值 $a_i$，且 $a_1, a_2, \ldots, a_n$ 构成一个 $0$ 到 $n-1$ 的排列。接下来你要依次检验 $m$ 条限制，每条限制会给定树上的两个结点 $x$ 和 $y$，你需要求出从 $x$ 到 $y$ 的简单路径上所有点的权值构成集合的 $\text{mex}$ 值。

对于一个集合 $S$，$\text{mex}(S)$ 表示最小的没有在 $S$ 中出现过的自然数。例如：

• $\text{mex}(0,1,2,5) = 3$
• $\text{mex}(1,2) = 0$

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, m$，分别表示用于结点数和限制条数。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示每个结点的权值。

接下来 $n-1$ 行每行包含两个整数，表示树上的一条边。

接下来 $m$ 行每行包含两个整数 $x_i, y_i$，表示一条限制。你需要求出从 $x_i$ 到 $y_i$ 的简单路径上所有点的权值构成集合的 $\text{mex}$ 值。

输出格式

输出到标准输出。

输出 $m$ 行每行一个正整数，第 $i$ 行的表示第 $i$ 条限制所需要求的 $\text{mex}$ 值。

7 3
1 0 2 6 3 4 5
1 2
2 5
2 6
1 3
3 7
1 4
5 3
6 3
7 4

4
3
0

子任务

对于所有数据，保证 $1 \leq n, m \leq 2 \times 10^5$。$a_1, a_2, \ldots, a_n$ 构成一个 $0$ 到 $n-1$ 的排列。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

特殊性质：保证给定的树是一条链。