路径上的最小点权

题目描述

给你一棵有 $n$ 个节点的树，节点编号从 $1$ 到 $n$，每个节点有一个点权 $a_i$。

有 $q$ 次询问，每次询问读入两个整数 $u,v$，请问从 $u$ 号点到 $v$ 号点的路径上的点的最小点权是多少。

输入格式

第一行两个整数 $n,q$，表示顶点数和询问数。

第二行 $n$ 个整数 $a_1,a_2,...,a_n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示 $u$ 号点和 $v$ 号点之间有一条边。

接下来 $q$ 行，每行两个整数 $u,v$ 代表一次询问。

输出格式

对于每个询问输出一行一个整数表示答案。

样例输入

3 3
1 2 3
1 2
2 3
1 2
1 3
2 3

样例输出

1
1
2

数据范围

对于 $100\%$ 的数据，保证 $1\leq n,q\leq 10^5, 1\leq a_i\leq 10^5, 1\leq u, v\leq n, u\neq v$，数据保证读入是一棵树。