#include <bits/stdc++.h>
using namespace std;
const int mn=80100;
vector<vector<int> > graf(mn);
int level_kurac[mn];
int lift[mn][25];
int p[mn];
int deg[mn];
void traverse(int node,int daddy)
{
    if(daddy==-1) level_kurac[node]=0;
    else
    {
        level_kurac[node]=level_kurac[daddy]+1;
        lift[node][0]=daddy;
    }
    for(int i=0;i<graf[node].size();i++)
    {
        if(graf[node][i]!=daddy)
        {
            traverse(graf[node][i],node);
        }
    }
}
void izresavaj_ga(int n)
{
    for(int j=1;j<25;j++)
    {
        for(int i=0;i<n;i++)
        {
            lift[i][j]=lift[lift[i][j-1]][j-1];
        }
    }
}
int jump(int node,int k)
{
    int ovde=0;
    while(k>0)
    {
        if(k%2==1) node=lift[node][ovde];
        k/=2;
        ovde++;
    }
    return node;
}
int lca(int a,int b)
{
    if(level_kurac[a]>level_kurac[b]) swap(a,b);
    int razlika=level_kurac[b]-level_kurac[a];
    b=jump(b,razlika);
    if(a==b) return a;
    for(int j=24;j>=0;j--)
    {
        if(lift[a][j]!=lift[b][j])
        {
            a=lift[a][j];
            b=lift[b][j];
        }
    }
    return lift[a][0];
}
int dist(int a,int b)
{
    int lcc=lca(a,b);
    return level_kurac[a]+level_kurac[b]-2*level_kurac[lcc];
}
struct Tree {
	typedef int T;
	static constexpr T unit = INT_MIN;
	T f(T a, T b) { return max(a, b); } // (any associative fn)
	vector<T> s; int n;
	Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
	void update(int pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(int b, int e) { // query [b, e)
		T ra = unit, rb = unit;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = f(ra, s[b++]);
			if (e % 2) rb = f(s[--e], rb);
		}
		return f(ra, rb);
	}
};
vector<int> lol;
int poz[mn];
void dfs(int node,int parent)
{
    lol.push_back(node);
    for(int i=0;i<graf[node].size();i++)
    {
        if(graf[node][i]!=parent)
        {
            dfs(graf[node][i],node);
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>p[i];
    for(int i=0;i<n;i++) p[i]--;
    for(int i=0;i<n-1;i++)
    {
        int xx,yy;
        cin>>xx>>yy;
        xx--; yy--;
        graf[xx].push_back(yy); graf[yy].push_back(xx);
        deg[xx]++; deg[yy]++;
    }
    traverse(0,-1);
    lift[0][0]=0;
    izresavaj_ga(n);
    int q;
    cin>>q;
    bool sabtask2=true;
    for(int i=0;i<n;i++)
    {
        if(deg[i]>2) sabtask2=false;
    }
    if(n<=4000 && q<=4000) //pazi ovde promeni!!!
    {
        while(q--)
        {
            int type;
            cin>>type;
            if(type==1)
            {
                int a,b;
                cin>>a>>b;
                a--; b--;
                swap(p[a],p[b]);
            }
            else
            {
                int l,r,x;
                cin>>l>>r>>x;
                l--; r--; x--;
                int mx=0;
                for(int i=l;i<=r;i++)
                {
                    mx=max(mx,dist(p[i],x));
                }
                cout<<mx<<endl;
            }
        }
    }
    else if(sabtask2)
    {
        //cerr<<"Sabtask2"<<endl;
        int sheeesh;
        for(int i=0;i<n;i++)
        {
            if(deg[i]==1)
            {
                sheeesh=i;
                break;
            }
        }
        //cerr<<sheeesh<<endl;
        dfs(sheeesh,-1);
        //cerr<<"Uradio dfs"<<endl;
        for(int i=0;i<n;i++)
        {
            poz[lol[i]]=i;
        }
        Tree Seg=Tree(n); //da nadjemo max
        Tree Segp=Tree(n); //da nadjemo min
        for(int i=0;i<n;i++) Seg.update(i,poz[p[i]]);
        for(int i=0;i<n;i++) Segp.update(i,-poz[p[i]]);
        while(q--)
        {
            int type;
            cin>>type;
            if(type==1)
            {
                int a,b;
                cin>>a>>b;
                a--; b--;
                int poma=Seg.query(a,a+1);
                int pomb=Seg.query(b,b+1);
                Seg.update(a,pomb);
                Seg.update(b,poma);
                poma=Segp.query(a,a+1);
                pomb=Segp.query(b,b+1);
                Segp.update(a,pomb);
                Segp.update(b,poma);
                //for(int i=0;i<n;i++) cerr<<Seg.query(i,i+1)<<" "<<Segp.query(i,i+1)<<endl;
            }
            else
            {
                int l,r,x;
                cin>>l>>r>>x;
                l--; r--; x--;
                int najveci=Seg.query(l,r+1);
                int najmanji=-Segp.query(l,r+1);
                //cerr<<najveci<<" "<<najmanji<<endl;
                cout<<max(abs(poz[x]-najveci),abs(poz[x]-najmanji))<<endl;
            }
        }
    }
    else //x=1 uvek
    {
        Tree Seg(n);
        for(int i=0;i<n;i++) Seg.update(i,level_kurac[p[i]]);
        while(q--)
        {
            int type;
            cin>>type;
            if(type==1)
            {
                int a,b;
                cin>>a>>b;
                a--; b--;
                int poma=Seg.query(a,a+1);
                int pomb=Seg.query(b,b+1);
                Seg.update(a,pomb);
                Seg.update(b,poma);
            }
            else
            {
                int a,b,x;
                cin>>a>>b>>x;
                a--; b--; x--;
                cout<<Seg.query(a,b+1)<<endl;
            }
        }
    }
}