#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,res,Q,K,u1,u2,vec,man,perm[80005],root,dist[80005],stmin[265000],stmax[265000],tip,l,r,x,dfsa[4005],dfspok,udaljenost[4005][4005];
bool prosli[80005],sl2=true,sl3=true,sl4=true;
vector<int> stablo[80005];
void dfs2(int gde,int dub){
   prosli[gde]=true;
   dist[gde]=dub;
   for(int i=0;i<stablo[gde].size();i++)
      if(!prosli[stablo[gde][i]])
         dfs2(stablo[gde][i],dub+1);
   return;
}
void update2(int gde){
   gde/2;
   while(gde>=1){
      stmax[gde]=max(stmax[gde*2],stmax[gde*2+1]);
      stmin[gde]=min(stmin[gde*2],stmin[gde*2+1]);
      gde/=2;
   }
   return;
}
ll getmax(int gde,int lg,int dg,int lc,int dc){
   if(lg==lc and dg==dc)
      return stmax[gde];
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return getmax(gde*2,lg,dg,lc,sred);
   if(lg>sred)
      return getmax(gde*2+1,lg,dg,sred+1,dc);
   ll v1,v2;
   v1=getmax(gde*2,lg,sred,lc,sred);
   v2=getmax(gde*2+1,sred+1,dg,sred+1,dc);
   return max(v1,v2);
}
ll getmin(int gde,int lg,int dg,int lc,int dc){
   if(lg==lc and dg==dc)
      return stmin[gde];
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return getmin(gde*2,lg,dg,lc,sred);
   if(lg>sred)
      return getmin(gde*2+1,lg,dg,sred+1,dc);
   ll v1,v2;
   v1=getmin(gde*2,lg,sred,lc,sred);
   v2=getmin(gde*2+1,sred+1,dg,sred+1,dc);
   return min(v1,v2);
}
void dfs1(int gde,int dub){
   dfsa[gde]=dfspok;
   udaljenost[dfspok][gde]=dub;
   for(int i=0;i<stablo[gde].size();i++)
      if(dfsa[stablo[gde][i]]<dfspok)
         dfs1(stablo[gde][i],dub+1);
   return;
}
struct query{
   int tip,l,r,x;
}qniz[80005];
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin>>N;
   for(int i=1;i<=N;i++)
      cin>>perm[i];
   for(int i=1;i<N;i++){
      cin>>u1>>u2;
      stablo[u1].push_back(u2);
      stablo[u2].push_back(u1);
      if(stablo[u1].size()>2 or stablo[u2].size()>2)
         sl2=false;
   }
   cin>>Q;
   if(N<=4000 and Q<=4000){
      for(dfspok=1;dfspok<=N;dfspok++)
         dfs1(dfspok,0);
      while(Q--){
         cin>>tip;
         if(tip==1){
            cin>>l>>r;
            swap(perm[l],perm[r]);
            continue;
         }
         res=0;
         cin>>l>>r>>x;
         for(int i=l;i<=r;i++)
            res=max(res,udaljenost[x][perm[i]]);
         cout<<res<<endl;
      }
      return 0;
   }
   if(sl2){
      for(int i=1;i<=N;i++)
         if(stablo[i].size()==1){
            root=i;
            break;
         }
      memset(stmin,1e9,sizeof(stmin));
      dfs2(root,0);
      K=1;
      while(K<N)
         K*=2;
      for(int i=1;i<=N;i++)
         stmax[K+i-1]=stmin[K+i-1]=dist[perm[i]];
      for(int i=K-1;i>=1;i--){
         stmax[i]=max(stmax[i*2],stmax[i*2+1]);
         stmin[i]=min(stmin[i*2],stmin[i*2+1]);
      }
      while(Q--){
         cin>>tip;
         if(tip==1){
            cin>>l>>r;
            swap(stmin[perm[l]+K-1],stmin[perm[r]+K-1]);
            //cout<<stmin[perm[l]+K-1]<<" "<<stmin[perm[r]+K-1]<<endl;
            swap(stmax[perm[l]+K-1],stmax[perm[r]+K-1]);
            //cout<<stmax[perm[l]+K-1]<<" "<<stmax[perm[r]+K-1]<<endl;
            update2(perm[l]+K-1);
            update2(perm[r]+K-1);
            continue;
         }
         cin>>l>>r>>x;
         vec=getmax(1,l,r,1,K);
         man=getmin(1,l,r,1,K);
       //  cout<<man<<" "<<vec<<endl;
         cout<<max(abs(dist[x]-vec),abs(dist[x]-man))<<endl;
      }
      return 0;
   }
   for(int i=1;i<=Q;i++){
      cin>>qniz[i].tip>>qniz[i].l>>qniz[i].r;
      if(qniz[i].tip==2){
         cin>>qniz[i].x;
         if(qniz[i].x!=1)
            sl3=false;
      }
      if(qniz[i].tip==1){
         sl4=false;
      }
   }
   if(sl3){
      dfs2(1,0);
      K=1;
      while(K<N)
         K*=2;
      for(int i=1;i<=N;i++)
         stmax[K+i-1]=dist[perm[i]];
      for(int i=K-1;i>=1;i--)
         stmax[i]=max(stmax[i*2],stmax[i*2+1]);
      for(int i=1;i<=Q;i++){
         if(qniz[i].tip==1){
            swap(stmax[perm[qniz[i].l]+K-1],stmax[perm[qniz[i].r]+K-1]);
            cout<<stmax[perm[qniz[i].l]+K-1]<<" "<<stmax[perm[qniz[i].r]+K-1]<<endl;
            swap(perm[qniz[i].l],perm[qniz[i].r]);
            update2(perm[qniz[i].l]+K-1);
            update2(perm[qniz[i].r]+K-1);
            continue;
         }
         cout<<getmax(1,qniz[i].l,qniz[i].r,1,K)<<endl;
      }
      return 0;
   }
}
/*
13
1 2 3 4 5 6 7 8 9 10 11 12 13
1 2
2 3
2 4
1 5
5 6
6 7
5 8
5 9
1 10
10 11
10 12
12 13
8
2 2 5 1
2 2 8 1
2 10 13 1
1 10 7
1 4 13
2 2 5 1
2 2 8 1
2 10 13 1


2
3
3
3
3
3
*/