#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=50000+100;
int deep[maxn],fa[maxn][20];
int u=1,v=1,time;
bool vis[maxn];
int st[maxn],top;
int R[maxn],unit,block;
int n,m;
int ans[maxn];
int tmp[maxn];
int Ans[maxn];
vector<int>G[maxn];
inline void dfs(int u){
for(int i=1;;i++){
if((1<<i)>deep[u]) break;
fa[u][i]=fa[fa[u][i-1]][i-1];
}
int len=G[u].size();
int bottom=top;
for(int i=0;i<len;i++){
int v=G[u][i];
if(fa[v][0]) continue;
fa[v][0]=u;
deep[v]=deep[u]+1;
dfs(v);
if(top-bottom>=unit){
block++;
while(top!=bottom) R[st[top--]]=block;
}
}
st[++top]=u;
}
inline int LCA(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
int dis=deep[x]-deep[y];
for(int i=0;;i++){
if((1<<i)>dis) break;
if((1<<i)&dis) x=fa[x][i];
}
if(x==y) return x;
for(int i=20;i>=0;i--){
if(deep[x]<(1<<i)) continue;
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
struct Moq{
int u,v;
int Time;
int id;
}moq[maxn];
int tot;
struct Moc{
int ind;
int New;
int Old;
}moc[maxn];
int T;
inline bool cmp(Moq a,Moq b){
return R[a.u]==R[b.u]?(R[a.v]==R[b.v]?a.Time<b.Time:R[a.v]<R[b.v]):R[a.u]<R[b.u];
}
struct BlockData{
struct {
int l,r;
}oneblock[350];
int n,unit,block_num,num[maxn],R[maxn],sum[350];
void init(){
unit=sqrt(n);
block_num=(n-1)/unit+1;
for(int i=1;i<=n;i++) R[i]=(i-1)/unit+1;
for(int i=1;i<=block_num;i++) oneblock[i].l=(i-1)*unit+1,oneblock[i].r=i*unit;
oneblock[block_num].r=n;
}
inline void Add(int ind){
if(ind<=n) sum[R[ind]]+=((++num[ind])==1);
}
inline void Del(int ind){
if(ind<=n) sum[R[ind]]-=((--num[ind])==0);
}
inline int getMin(){
for(int i=1;i<=block_num;i++){
if(sum[i]!=(oneblock[i].r-oneblock[i].l+1))
for(int j=oneblock[i].l;j<=oneblock[i].r;j++)
if(!num[j]) return j;
}
}
}Data;
inline void kaven(int ind,int v){
if(vis[ind]){
Data.Del(ans[ind]);
Data.Add(v);
}
ans[ind]=v;
}
inline void Run(int ind){
if(vis[ind]) Data.Del(ans[ind]),vis[ind]=0;
else Data.Add(ans[ind]),vis[ind]=1;
}
inline void move(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
while(deep[x]>deep[y]) Run(x),x=fa[x][0];
while(x!=y) Run(x),Run(y),x=fa[x][0],y=fa[y][0];
}
void Mo(){
for(int i=1;i<=tot;i++){
while(time<moq[i].Time) time++,kaven(moc[time].ind,moc[time].New);
while(time>moq[i].Time) kaven(moc[time].ind,moc[time].Old),time--;
if(u!=moq[i].u) move(u,moq[i].u),u=moq[i].u;
if(v!=moq[i].v) move(v,moq[i].v),v=moq[i].v;
int lca=LCA(u,v);
Run(lca);
Ans[moq[i].id]=Data.getMin()-1;
Run(lca);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&ans[i]),tmp[i]=++ans[i];
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
unit=sqrt(n);
dfs(1);
while(top) R[st[top--]]=block;
for(int i=1;i<=m;i++){
int sign,x,y;
scanf("%d%d%d",&sign,&x,&y);
if(sign){
moq[++tot].u=x;
moq[tot].v=y;
moq[tot].Time=T;
moq[tot].id=tot;
}
else{
moc[++T].ind=x;
moc[T].New=y+1;
moc[T].Old=tmp[x];
tmp[x]=y+1;
}
}
sort(moq+1,moq+1+tot,cmp);
Data.n=n+1;
Data.init();
Mo();
for(int i=1;i<=tot;i++) printf("%d\n",Ans[i]);
}
