You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.

We will ask you to perform the following operation:

• u v : ask for how many different integers that represent the weight of nodes there are on the path from u tov.

Input

In the first line there are two integers N and M. (N <= 40000, M <= 100000)

In the second line there are N integers. The i-th integer denotes the weight of the i-th node.

In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).

In the next M lines, each line contains two integers u v, which means an operation asking for how many different integers that represent the weight of nodes there are on the path from u to v.

Output

For each operation, print its result.

Example

Input:8 2105 2 9 3 8 5 7 71 21 31 43 53 63 74 82 57 8

Output:44

#include<cmath>#include<cstdio>#include<algorithm>using namespace std;#define N 40001#define M 100001int n,m,siz,tmp;int hash[N],key[N];int front[N],to[N*2],nxt[N*2],tot;int fa[N],deep[N],id[N],son[N],bl[N],block[N];bool vis[N];int sum[N],ans[M];struct node{    int l,r,id;    bool operator < (node p) const    {        if(block[l]!=block[p.l]) return block[l]<block[p.l];        return block[r]<block[p.r];    }}e[M];int read(int &x){    x=0; char c=getchar();    while(c<‘0‘||c>‘9‘) c=getchar();    while(c>=‘0‘&&c<=‘9‘) { x=x*10+c-‘0‘; c=getchar(); }}void add(int x,int y){    to[++tot]=y; nxt[tot]=front[x]; front[x]=tot;    to[++tot]=x; nxt[tot]=front[y]; front[y]=tot;}void dfs(int x){    son[x]++;    for(int i=front[x];i;i=nxt[i])    {        if(to[i]==fa[x]) continue;        deep[to[i]]=deep[x]+1;        fa[to[i]]=x;        dfs(to[i]);        son[x]+=son[to[i]];    }}void dfs2(int x,int top){    id[x]=++tot;    bl[x]=top;    block[x]=(tot-1)/siz+1;    int y=0;    for(int i=front[x];i;i=nxt[i])    {        if(to[i]==fa[x]) continue;        if(son[to[i]]>son[y]) y=to[i];    }    if(!y) return;    dfs2(y,top);    for(int i=front[x];i;i=nxt[i])    {        if(to[i]==fa[x]||to[i]==y) continue;        dfs2(to[i],to[i]);    }}void point(int u){    if(vis[u]) tmp-=(!--sum[hash[u]]);    else tmp+=(++sum[hash[u]]==1);    vis[u]^=1;}void path(int u,int v){    while(u!=v)    {        if(deep[u]>deep[v]) point(u),u=fa[u];        else point(v),v=fa[v];    }}int get_lca(int u,int v){    while(bl[u]!=bl[v])    {        if(deep[bl[u]]<deep[bl[v]]) swap(u,v);        u=fa[bl[u]];    }    return deep[u]<deep[v] ? u : v;}int main(){    read(n);read(m);  siz=sqrt(n);    for(int i=1;i<=n;i++) read(key[i]),hash[i]=key[i];    sort(key+1,key+n+1);    key[0]=unique(key+1,key+n+1)-(key+1);    for(int i=1;i<=n;i++) hash[i]=lower_bound(key+1,key+key[0]+1,hash[i])-key;    int x,y;    for(int i=1;i<n;i++)    {        read(x); read(y);        add(x,y);    }    tot=0;    dfs(1);    dfs2(1,1);    for(int i=1;i<=m;i++)    {        read(e[i].l); read(e[i].r);        e[i].id=i;    }    sort(e+1,e+m+1);    int L=1,R=1,lca;    for(int i=1;i<=m;i++)    {        if(id[e[i].l]>id[e[i].r]) swap(e[i].l,e[i].r);        path(L,e[i].l);        path(R,e[i].r);        lca=get_lca(e[i].l,e[i].r);        point(lca);        ans[e[i].id]=tmp;        point(lca);        L=e[i].l; R=e[i].r;    }    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);}