#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int belong[maxn],be[maxn],first[maxn],tot,cnt,top,deep[maxn],f[maxn][],B,Q;

int st[maxn],c[maxn],n,m,c0,c1,sz[maxn],num[maxn],mx,pre[maxn],ANS[maxn];

bool vis[maxn];

struct edge{int v,from;}e[maxn*];

struct mo{int x,y,pre;}a[maxn];

struct que{int x,y,t,id;}b[maxn];

bool cmp(que a,que b){return belong[a.x]<belong[b.x]||(belong[a.x]==belong[b.x]&&belong[a.y]<belong[b.y])||

(belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y]&&a.t<b.t);}

void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}

void dfs(int x,int fa){

    int p=top;

    for(int j=;(<<j)<=deep[x];j++)f[x][j]=f[f[x][j-]][j-];

    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){

        deep[e[i].v]=deep[x]+;

        f[e[i].v][]=x;

        dfs(e[i].v,x);

        if(top-p>=B){

            cnt++;

            while(top>p)belong[st[top--]]=cnt;

        }

    }

    st[++top]=x;//

}

int lca(int x,int y){

    if(deep[x]<deep[y])swap(x,y);

    int d=deep[x]-deep[y];

    for(int j=;(<<j)<=d;j++)if(d&(<<j))x=f[x][j];

    if(x==y)return x;

    for(int j=;j>=;j--)if((<<j)<=deep[x]&&f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];

    return f[x][];

}

void rev(int x){

    if(c[x]>n){vis[x]^=;return;}

    if(!vis[x])sz[be[c[x]]]+=(++num[c[x]]==);

    else sz[be[c[x]]]-=(--num[c[x]]==);

    vis[x]^=;

}

void modify(int x,int y){

    if(!vis[x])c[x]=y;

    else rev(x),c[x]=y,rev(x);

}

void solve(int x,int y){

    while(x!=y){

        if(deep[x]>deep[y])rev(x),x=f[x][];

        else rev(y),y=f[y][];

    }

}

int calc(){

    int r;

    for(r=;r<mx;r++)if(sz[r]<Q)break;

    for(int i=r*Q;i<=n;i++)if(num[i]==)return i;

    return n;

}

int main(){

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

    for(int i=;i<=n;i++)scanf("%d",&c[i]),pre[i]=c[i];

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

        int u,v;

        scanf("%d%d",&u,&v);

        insert(u,v);insert(v,u);

    }

    B=(int)(pow(n,2.0/)*0.5)+;

    Q=(int)(sqrt(n))+;

    for(int i=;i<=n;i++)be[i]=i/Q;mx=n/Q;

    dfs(,);

    while(top)belong[st[top--]]=cnt;

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

        int s,u,v;

        scanf("%d%d%d",&s,&u,&v);

        if(!s)a[++c0]=(mo){u,v,pre[u]},pre[u]=v;

        else{

            if(belong[u]>belong[v])swap(u,v);

            b[++c1]=(que){u,v,c0,c1};

        }

    }

    sort(b+,b+c1+,cmp);

    for(int i=;i<=b[].t;i++)modify(a[i].x,a[i].y);

    solve(b[].x,b[].y);

    int L=lca(b[].x,b[].y);

    rev(L);ANS[b[].id]=calc();rev(L);

    for(int i=;i<=c1;i++){///

        for(int j=b[i-].t+;j<=b[i].t;j++)modify(a[j].x,a[j].y);

        for(int j=b[i-].t;j>b[i].t;j--)modify(a[j].x,a[j].pre);

        solve(b[i-].x,b[i].x);solve(b[i-].y,b[i].y);

        int L=lca(b[i].x,b[i].y);

        rev(L);ANS[b[i].id]=calc();rev(L);

    }

    for(int i=;i<=c1;i++)printf("%d\n",ANS[i]);

    return ;

}