#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define N 50001

int v[N<<1],en,first[N],next[N<<1];

void AddEdge(int U,int V)

{

    v[++en]=V;

    next[en]=first[U];

    first[U]=en;

}

int n,m,a[N],b[N];

int eq,ec,blo,sz,siz[N],top[N],fa[N],dep[N],num[N];

void dfs(int U)

{

    for(int i=first[U];i;i=next[i])

      if(v[i]!=fa[U])

        {

          fa[v[i]]=U;

          dep[v[i]]=dep[U]+1;

          if(siz[top[U]]<sz)

            {

              ++siz[top[U]];

              top[v[i]]=top[U];

            }

          dfs(v[i]);

        }

}

void df2(int U)

{

    num[U]=blo;

    for(int i=first[U];i;i=next[i])

      if(v[i]!=fa[U]&&top[v[i]]==top[U])

        df2(v[i]);

}

int lca(int U,int V)

{

    while(U!=V)

      {

        if(top[U]!=top[V])

          {

            if(dep[top[U]]<dep[top[V]])

              swap(U,V);

            U=fa[top[U]];

          }

        else

          {

            if(dep[U]<dep[V])

              swap(U,V);

            U=fa[U];

          }

      }

    return U;

}

struct UPT{int x,y,z;}CH[N];

struct ASK{int l,r,p,t;}Q[N];

bool operator < (const ASK &a,const ASK &b)

{

    if(num[a.l]==num[b.l])

      {

        if(num[a.r]==num[b.r])

          return a.t<b.t;

        return num[a.r]<num[b.r];

      }

    return num[a.l]<num[b.l];

}

int nu2[N],r[230],l[230],sumv[230],bl2=1,T[N];

void makeblock()

{

    int sz=sqrt(n); if(!sz) sz=0;

    r[0]=-1;

    for(;bl2*sz<n;++bl2)

      {

        l[bl2]=r[bl2-1]+1;

        r[bl2]=bl2*sz;

        for(int i=l[bl2];i<=r[bl2];++i)

          nu2[i]=bl2;

      }

    l[bl2]=r[bl2-1]+1;

    r[bl2]=n;

    for(int i=l[bl2];i<=r[bl2];++i)

      nu2[i]=bl2;

}

void Update(int x,int op)

{

    if(x>=n)

      return;

    T[x]+=op;

    if(!T[x])

      --sumv[nu2[x]];

    else if(op==1&&T[x]==1)

      ++sumv[nu2[x]];

}

bool vis[N];

void Work(int U,int V,int LCA)

{

    while(U!=LCA)

      {

        vis[U]^=1;

        Update(a[U],vis[U]?1:-1);

        U=fa[U];

      }

    while(V!=LCA)

      {

        vis[V]^=1;

        Update(a[V],vis[V]?1:-1);

        V=fa[V];

      }

}

int Query()

{

    for(int i=1;i<=bl2;++i)

      if(sumv[i]<r[i]-l[i]+1)

        for(int j=l[i];j<=r[i];++j)

          if(!T[j])

            return j;

}

bool op[N];

int anss[N];

int main()

{

    int x,y;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;++i)

      scanf("%d",&a[i]);

    for(int i=1;i<n;++i)

      {

         scanf("%d%d",&x,&y);

         AddEdge(x,y);

         AddEdge(y,x);

      }

    for(int i=1;i<=n;++i)

      {

        top[i]=i;

        siz[i]=1;

      }

    sz=(int)pow((double)n,2.0/3.0);

    dfs(1);

    for(int i=1;i<=n;++i)

      if(top[i]==i)

        {

          ++blo;

          df2(i);

        }

    memcpy(b,a,sizeof(int)*(n+1));

    for(int i=1;i<=m;++i)

      {

        scanf("%d",&op[i]);

        if(!op[i])

          {

            ++ec;

            scanf("%d%d",&CH[ec].x,&CH[ec].y);

            CH[ec].z=b[CH[ec].x];

            b[CH[ec].x]=CH[ec].y;

          }

        else

          {

            ++eq;

            scanf("%d%d",&Q[eq].l,&Q[eq].r);

            Q[eq].t=ec; Q[eq].p=eq;

          }

      }

    makeblock();

    sort(Q+1,Q+eq+1);

    for(int i=1;i<=Q[1].t;++i)

      a[CH[i].x]=CH[i].y;

    int LCA=lca(Q[1].l,Q[1].r);

    Work(Q[1].l,Q[1].r,LCA);

    Update(a[LCA],1);

    anss[Q[1].p]=Query();

    Update(a[LCA],-1);

    for(int i=2;i<=eq;++i)

      {

        if(Q[i-1].t<Q[i].t) for(int j=Q[i-1].t+1;j<=Q[i].t;++j)

          {

            if(vis[CH[j].x])

              {

                Update(CH[j].y,1);

                Update(a[CH[j].x],-1);

              }

            a[CH[j].x]=CH[j].y;

          }

        else for(int j=Q[i-1].t;j>Q[i].t;--j)

          {

            if(vis[CH[j].x])

              {

                Update(CH[j].z,1);

                Update(a[CH[j].x],-1);

              }

            a[CH[j].x]=CH[j].z;

          }

        Work(Q[i-1].l,Q[i].l,lca(Q[i-1].l,Q[i].l));

        Work(Q[i-1].r,Q[i].r,lca(Q[i-1].r,Q[i].r));

        LCA=lca(Q[i].l,Q[i].r);

        Update(a[LCA],1);

        anss[Q[i].p]=Query();

        Update(a[LCA],-1);

      }

    for(int i=1;i<=eq;++i)

      printf("%d\n",anss[i]);

    return 0;

}