// Kirito's official solution to year2018p6 - Old Christmas Lights II
#include<bits/stdc++.h>
const int MAXN=5e4+4,MAXQ=5e4+4,RT=800,MAXLN=18,INF=0x3f3f3f3f;
int N,Q,cnt,C[MAXN],depth[MAXN],ans[MAXN],ein[MAXN],eout[MAXN],eid[MAXN<<1],st[MAXN][MAXLN];
struct qry {
int l,r,lca,i;
bool operator <(const qry &q) const {
return l/RT<q.l/RT||(l/RT==q.l/RT&&r<q.r);
}
}qrys[MAXQ];
std::vector<int>adj[MAXN];
std::multiset<int>S,diff;
std::bitset<MAXN>seen;
void dfs(int src,int p,int d=1) {
eid[ein[src]=++cnt]=src;
st[src][0]=p;
depth[src]=d++;
for(int i:adj[src]) {
if(i==p) continue;
dfs(i,src,d);
}
eid[eout[src]=++cnt]=src;
}
inline void build() {
for(int j=1;j<MAXLN;++j)
for(int i=1;i<=N;++i)
if(~st[i][j-1])
st[i][j]=st[st[i][j-1]][j-1];
else
st[i][j]=-1;
}
inline int lca(int a,int b) {
if(depth[a]<depth[b]) std::swap(a,b);
for(int i=MAXLN-1;i>=0;--i)
if(~st[a][i]&&depth[st[a][i]]>=depth[b])
a=st[a][i];
if(a==b) return a;
for(int i=MAXLN-1;i>=0;--i)
if(st[a][i]!=st[b][i])
a=st[a][i],b=st[b][i];
return st[a][0];
}
inline void moUpd(int t){
seen.flip(t);
if(seen[t]){
if(S.size()==1)
diff.insert(abs(C[t]-*S.begin()));
else if(S.size()>1) {
auto x=S.lower_bound(C[t]);
if(x==S.begin())
diff.insert(*x-C[t]);
else {
auto y=std::prev(x);
if(x==S.end())
diff.insert(C[t]-*y);
else{
diff.erase(diff.lower_bound(*x-*y));
diff.insert(C[t]-*y);
diff.insert(*x-C[t]);
}
}
}
S.insert(C[t]);
}else{
S.erase(S.find(C[t]));
if(S.size()==1)
diff.erase(diff.lower_bound(abs(C[t]-*S.begin())));
else if(S.size()>1) {
auto x=S.lower_bound(C[t]);
if(x==S.begin())
diff.erase(diff.lower_bound(*x-C[t]));
else {
auto y=std::prev(x);
if(x==S.end())
diff.erase(diff.lower_bound(C[t]-*y));
else{
diff.insert(*x-*y);
diff.erase(diff.lower_bound(C[t]-*y));
diff.erase(diff.lower_bound(*x-C[t]));
}
}
}
}
}
int main() {
assert(scanf("%d%d",&N,&Q)==2);
for(int i=1;i<=N;assert(scanf("%d",C+i++)==1));
for(int i=1,a,b;i<N;++i) {
assert(scanf("%d%d",&a,&b)==2);
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
dfs(1,-1);
build();
for(int i=0,a,b,l;i<Q;++i) {
assert(scanf("%d%d",&a,&b)==2);
l=lca(a,b);
if(ein[a]>ein[b]) std::swap(a,b);
if(a==l||b==l)
qrys[i]={ein[a],ein[b],-1,i};
else
qrys[i]={eout[a],ein[b],C[l],i};
}
std::sort(qrys,qrys+Q);
for(int i=0,l=0,r=0,lst=-1;i<Q;++i) {
if(lst!=qrys[i].l/RT) {
S.clear();
diff.clear();
seen.reset();
moUpd(eid[l=r=qrys[i].l]);
lst=qrys[i].l/RT;
}
while(r<qrys[i].r)
moUpd(eid[++r]);
while(l>qrys[i].l)
moUpd(eid[--l]);
while(l<qrys[i].l)
moUpd(eid[l++]);
while(r>qrys[i].r)
moUpd(eid[r--]);
ans[qrys[i].i]=*diff.begin();
if(~qrys[i].lca) {
if(S.size()==1)
ans[qrys[i].i]=std::min(ans[qrys[i].i],abs(qrys[i].lca-*S.begin()));
else if(S.size()>1) {
auto x=S.lower_bound(qrys[i].lca);
int oth=INF;
if(x==S.begin())
oth=*x-qrys[i].lca;
else {
auto y=std::prev(x);
if(x==S.end())
oth=qrys[i].lca-*y;
else
oth=std::min(*x-qrys[i].lca,qrys[i].lca-*y);
}
ans[qrys[i].i]=std::min(ans[qrys[i].i],oth);
}
}
}
for(int i=0;i<Q;printf("%d\n",ans[i++]));
}
Ly8gS2lyaXRvJ3Mgb2ZmaWNpYWwgc29sdXRpb24gdG8geWVhcjIwMThwNiAtIE9sZCBDaHJpc3RtYXMgTGlnaHRzIElJCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CmNvbnN0IGludCBNQVhOPTVlNCs0LE1BWFE9NWU0KzQsUlQ9ODAwLE1BWExOPTE4LElORj0weDNmM2YzZjNmOwppbnQgTixRLGNudCxDW01BWE5dLGRlcHRoW01BWE5dLGFuc1tNQVhOXSxlaW5bTUFYTl0sZW91dFtNQVhOXSxlaWRbTUFYTjw8MV0sc3RbTUFYTl1bTUFYTE5dOwpzdHJ1Y3QgcXJ5IHsKICAgIGludCBsLHIsbGNhLGk7CiAgICBib29sIG9wZXJhdG9yIDwoY29uc3QgcXJ5ICZxKSBjb25zdCB7CiAgICAgICAgcmV0dXJuIGwvUlQ8cS5sL1JUfHwobC9SVD09cS5sL1JUJiZyPHEucik7CiAgICB9Cn1xcnlzW01BWFFdOwpzdGQ6OnZlY3RvcjxpbnQ+YWRqW01BWE5dOwpzdGQ6Om11bHRpc2V0PGludD5TLGRpZmY7CnN0ZDo6Yml0c2V0PE1BWE4+c2VlbjsKdm9pZCBkZnMoaW50IHNyYyxpbnQgcCxpbnQgZD0xKSB7CiAgICBlaWRbZWluW3NyY109KytjbnRdPXNyYzsKICAgIHN0W3NyY11bMF09cDsKICAgIGRlcHRoW3NyY109ZCsrOwogICAgZm9yKGludCBpOmFkaltzcmNdKSB7CiAgICAgICAgaWYoaT09cCkgY29udGludWU7CiAgICAgICAgZGZzKGksc3JjLGQpOwogICAgfQogICAgZWlkW2VvdXRbc3JjXT0rK2NudF09c3JjOwp9CmlubGluZSB2b2lkIGJ1aWxkKCkgewogICAgZm9yKGludCBqPTE7ajxNQVhMTjsrK2opCiAgICAgICAgZm9yKGludCBpPTE7aTw9TjsrK2kpCiAgICAgICAgICAgIGlmKH5zdFtpXVtqLTFdKQogICAgICAgICAgICAgICAgc3RbaV1bal09c3Rbc3RbaV1bai0xXV1bai0xXTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgc3RbaV1bal09LTE7Cn0KaW5saW5lIGludCBsY2EoaW50IGEsaW50IGIpIHsKICAgIGlmKGRlcHRoW2FdPGRlcHRoW2JdKSBzdGQ6OnN3YXAoYSxiKTsKICAgIGZvcihpbnQgaT1NQVhMTi0xO2k+PTA7LS1pKQogICAgICAgIGlmKH5zdFthXVtpXSYmZGVwdGhbc3RbYV1baV1dPj1kZXB0aFtiXSkKICAgICAgICAgICAgYT1zdFthXVtpXTsKICAgIGlmKGE9PWIpIHJldHVybiBhOwogICAgZm9yKGludCBpPU1BWExOLTE7aT49MDstLWkpCiAgICAgICAgaWYoc3RbYV1baV0hPXN0W2JdW2ldKQogICAgICAgICAgICBhPXN0W2FdW2ldLGI9c3RbYl1baV07CiAgICByZXR1cm4gc3RbYV1bMF07Cn0KaW5saW5lIHZvaWQgbW9VcGQoaW50IHQpewogICAgc2Vlbi5mbGlwKHQpOwogICAgaWYoc2Vlblt0XSl7CiAgICAgICAgaWYoUy5zaXplKCk9PTEpCiAgICAgICAgICAgIGRpZmYuaW5zZXJ0KGFicyhDW3RdLSpTLmJlZ2luKCkpKTsKICAgICAgICBlbHNlIGlmKFMuc2l6ZSgpPjEpIHsKICAgICAgICAgICAgYXV0byB4PVMubG93ZXJfYm91bmQoQ1t0XSk7CiAgICAgICAgICAgIGlmKHg9PVMuYmVnaW4oKSkKICAgICAgICAgICAgICAgIGRpZmYuaW5zZXJ0KCp4LUNbdF0pOwogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIGF1dG8geT1zdGQ6OnByZXYoeCk7CiAgICAgICAgICAgICAgICBpZih4PT1TLmVuZCgpKQogICAgICAgICAgICAgICAgICAgIGRpZmYuaW5zZXJ0KENbdF0tKnkpOwogICAgICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgICAgICBkaWZmLmVyYXNlKGRpZmYubG93ZXJfYm91bmQoKngtKnkpKTsKICAgICAgICAgICAgICAgICAgICBkaWZmLmluc2VydChDW3RdLSp5KTsKICAgICAgICAgICAgICAgICAgICBkaWZmLmluc2VydCgqeC1DW3RdKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBTLmluc2VydChDW3RdKTsKICAgIH1lbHNlewogICAgICAgIFMuZXJhc2UoUy5maW5kKENbdF0pKTsKICAgICAgICBpZihTLnNpemUoKT09MSkKICAgICAgICAgICAgZGlmZi5lcmFzZShkaWZmLmxvd2VyX2JvdW5kKGFicyhDW3RdLSpTLmJlZ2luKCkpKSk7CiAgICAgICAgZWxzZSBpZihTLnNpemUoKT4xKSB7CiAgICAgICAgICAgIGF1dG8geD1TLmxvd2VyX2JvdW5kKENbdF0pOwogICAgICAgICAgICBpZih4PT1TLmJlZ2luKCkpCiAgICAgICAgICAgICAgICBkaWZmLmVyYXNlKGRpZmYubG93ZXJfYm91bmQoKngtQ1t0XSkpOwogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIGF1dG8geT1zdGQ6OnByZXYoeCk7CiAgICAgICAgICAgICAgICBpZih4PT1TLmVuZCgpKQogICAgICAgICAgICAgICAgICAgIGRpZmYuZXJhc2UoZGlmZi5sb3dlcl9ib3VuZChDW3RdLSp5KSk7CiAgICAgICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgICAgIGRpZmYuaW5zZXJ0KCp4LSp5KTsKICAgICAgICAgICAgICAgICAgICBkaWZmLmVyYXNlKGRpZmYubG93ZXJfYm91bmQoQ1t0XS0qeSkpOwogICAgICAgICAgICAgICAgICAgIGRpZmYuZXJhc2UoZGlmZi5sb3dlcl9ib3VuZCgqeC1DW3RdKSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KaW50IG1haW4oKSB7CiAgICBhc3NlcnQoc2NhbmYoIiVkJWQiLCZOLCZRKT09Mik7CiAgICBmb3IoaW50IGk9MTtpPD1OO2Fzc2VydChzY2FuZigiJWQiLEMraSsrKT09MSkpOwogICAgZm9yKGludCBpPTEsYSxiO2k8TjsrK2kpIHsKICAgICAgICBhc3NlcnQoc2NhbmYoIiVkJWQiLCZhLCZiKT09Mik7CiAgICAgICAgYWRqW2FdLmVtcGxhY2VfYmFjayhiKTsKICAgICAgICBhZGpbYl0uZW1wbGFjZV9iYWNrKGEpOwogICAgfQogICAgZGZzKDEsLTEpOwogICAgYnVpbGQoKTsKICAgIGZvcihpbnQgaT0wLGEsYixsO2k8UTsrK2kpIHsKICAgICAgICBhc3NlcnQoc2NhbmYoIiVkJWQiLCZhLCZiKT09Mik7CiAgICAgICAgbD1sY2EoYSxiKTsKICAgICAgICBpZihlaW5bYV0+ZWluW2JdKSBzdGQ6OnN3YXAoYSxiKTsKICAgICAgICBpZihhPT1sfHxiPT1sKQogICAgICAgICAgICBxcnlzW2ldPXtlaW5bYV0sZWluW2JdLC0xLGl9OwogICAgICAgIGVsc2UKICAgICAgICAgICAgcXJ5c1tpXT17ZW91dFthXSxlaW5bYl0sQ1tsXSxpfTsKICAgIH0KICAgIHN0ZDo6c29ydChxcnlzLHFyeXMrUSk7CiAgICBmb3IoaW50IGk9MCxsPTAscj0wLGxzdD0tMTtpPFE7KytpKSB7CiAgICAgICAgaWYobHN0IT1xcnlzW2ldLmwvUlQpIHsKICAgICAgICAgICAgUy5jbGVhcigpOwogICAgICAgICAgICBkaWZmLmNsZWFyKCk7CiAgICAgICAgICAgIHNlZW4ucmVzZXQoKTsKICAgICAgICAgICAgbW9VcGQoZWlkW2w9cj1xcnlzW2ldLmxdKTsKICAgICAgICAgICAgbHN0PXFyeXNbaV0ubC9SVDsKICAgICAgICB9CiAgICAgICAgd2hpbGUocjxxcnlzW2ldLnIpCiAgICAgICAgICAgIG1vVXBkKGVpZFsrK3JdKTsKICAgICAgICB3aGlsZShsPnFyeXNbaV0ubCkKICAgICAgICAgICAgbW9VcGQoZWlkWy0tbF0pOwogICAgICAgIHdoaWxlKGw8cXJ5c1tpXS5sKQogICAgICAgICAgICBtb1VwZChlaWRbbCsrXSk7CiAgICAgICAgd2hpbGUocj5xcnlzW2ldLnIpCiAgICAgICAgICAgIG1vVXBkKGVpZFtyLS1dKTsKICAgICAgICBhbnNbcXJ5c1tpXS5pXT0qZGlmZi5iZWdpbigpOwogICAgICAgIGlmKH5xcnlzW2ldLmxjYSkgewogICAgICAgICAgICBpZihTLnNpemUoKT09MSkKICAgICAgICAgICAgICAgIGFuc1txcnlzW2ldLmldPXN0ZDo6bWluKGFuc1txcnlzW2ldLmldLGFicyhxcnlzW2ldLmxjYS0qUy5iZWdpbigpKSk7CiAgICAgICAgICAgIGVsc2UgaWYoUy5zaXplKCk+MSkgewogICAgICAgICAgICAgICAgYXV0byB4PVMubG93ZXJfYm91bmQocXJ5c1tpXS5sY2EpOwogICAgICAgICAgICAgICAgaW50IG90aD1JTkY7CiAgICAgICAgICAgICAgICBpZih4PT1TLmJlZ2luKCkpCiAgICAgICAgICAgICAgICAgICAgb3RoPSp4LXFyeXNbaV0ubGNhOwogICAgICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgYXV0byB5PXN0ZDo6cHJldih4KTsKICAgICAgICAgICAgICAgICAgICBpZih4PT1TLmVuZCgpKQogICAgICAgICAgICAgICAgICAgICAgICBvdGg9cXJ5c1tpXS5sY2EtKnk7CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICBvdGg9c3RkOjptaW4oKngtcXJ5c1tpXS5sY2EscXJ5c1tpXS5sY2EtKnkpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgYW5zW3FyeXNbaV0uaV09c3RkOjptaW4oYW5zW3FyeXNbaV0uaV0sb3RoKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIGZvcihpbnQgaT0wO2k8UTtwcmludGYoIiVkXG4iLGFuc1tpKytdKSk7Cn0=