#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n, q, p[80002], sus[80002], d[80002], koji;
bool brsus, svix;
vector<pair<pii, int>> v;
vector<int> graf[80002];

void dfs(int node, int par, int dub) {
    d[node]=dub;
    for(auto adj:graf[node]) {
        if(adj==par) continue;
        dfs(adj, node, dub+1);
    }
}
pii st[320010];
void build(int node, int tl, int tr) {
    if(tl==tr) {
        st[node].xx=st[node].yy=d[p[tl-1]];
        return;
    }
    int mid=(tl+tr)/2;
    build(2*node, tl, mid);
    build(2*node+1, mid+1, tr);
    st[node].xx=min(st[2*node].xx, st[2*node+1].xx);
    st[node].yy=max(st[2*node].yy, st[2*node+1].yy);
}
void upd(int node, int tl, int tr, int poz, int val) {
    if(tl==tr) {
        st[node].xx=st[node].yy=val;
        return;
    }
    int mid=(tl+tr)/2;
    if(mid>=poz) upd(2*node, tl, mid, poz, val);
    else upd(2*node+1, mid+1, tr, poz, val);
    st[node].xx=min(st[2*node].xx, st[2*node+1].xx);
    st[node].yy=max(st[2*node].yy, st[2*node+1].yy);
}
pii query(int node, int tl, int tr, int gl, int gr) {
    if(tl>=gl && tr<=gr) return st[node];
    int mid=(tl+tr)/2;
    pii qq={2000000000, 0};
    if(mid>=gl) {
        pii qq1=query(2*node, tl, mid, gl, gr);
        qq.xx=min(qq.xx, qq1.xx);
        qq.yy=max(qq.yy, qq1.yy);
    }
    if(mid+1<=gr) {
        pii qq1=query(2*node+1, mid+1, tr, gl, gr);
        qq.xx=min(qq.xx, qq1.xx);
        qq.yy=max(qq.yy, qq1.yy);
    }
    return qq;
}
int main() {
    ios;
    cin >> n;
    brsus=svix=1;
    for(int i=0; i<n; i++) {
        cin >> p[i];
    }
    for(int i=0; i<n-1; i++) {
        int u, w; cin >> u >> w;
        graf[u].pb(w); graf[w].pb(u);
        sus[u]++, sus[w]++;
        if(sus[u]>2 || sus[w]>2) brsus=false;
        if(sus[u]==1) koji=u;
        else if(koji==u) koji=-1;
        if(sus[w]==1) koji=w;
        else if(koji==w) koji=-1;
    }
    cin >> q;
    v.resize(q);
    for(int i=0; i<q; i++) {
        int nes;
        cin >> nes >> v[i].xx.xx;
        if(nes==1) cin >> v[i].yy;
        else {
            cin >> v[i].xx.yy >> v[i].yy;
            if(v[i].yy!=1) svix=0;
        }
    }
    if(n<=4000 && q<=4000) { /// OBAVEZNO UKLONITI && FALSE OBAVEZNO
        for(int i=0; i<q; i++) {
            if(v[i].xx.yy==0) {
                swap(p[v[i].xx.xx-1], p[v[i].yy-1]);
            }
            else {
                dfs(v[i].yy, -1, 0);
                int maxi=0;
                for(int j=v[i].xx.xx-1; j<=v[i].xx.yy-1; j++) {
                    maxi=max(maxi, d[p[j]]);
                }
                cout << maxi << "\n";
            }
        }
    }
    else if(brsus) {
        dfs(koji, -1, 0);
        build(1, 1, n);
        for(int i=0; i<q; i++) {
            if(v[i].xx.yy==0) {
                int pr=p[v[i].xx.xx-1], dr=p[v[i].yy-1];
                upd(1, 1, n, v[i].xx.xx, d[dr]);
                upd(1, 1, n, v[i].yy, d[pr]);
                swap(p[v[i].xx.xx-1], p[v[i].yy-1]);
            }
            else {
                pii res=query(1, 1, n, v[i].xx.xx, v[i].xx.yy);
                //cout << res.xx << ' ' << res.yy << ' ';
                cout << max(abs(res.xx-d[v[i].yy]), abs(res.yy-d[v[i].yy])) << "\n";
            }
        }
    }
    else if(svix) {
        dfs(1, -1, 0);
        build(1, 1, n);
        for(int i=0; i<q; i++) {
            if(v[i].xx.yy==0) {
                int pr=p[v[i].xx.xx-1], dr=p[v[i].yy-1];
                upd(1, 1, n, v[i].xx.xx, d[dr]);
                upd(1, 1, n, v[i].yy, d[pr]);
                swap(p[v[i].xx.xx-1], p[v[i].yy-1]);
            }
            else {
                pii res=query(1, 1, n, v[i].xx.xx, v[i].xx.yy);
                //cout << res.xx << ' ' << res.yy << ' ';
                cout << max(abs(res.xx-d[v[i].yy]), abs(res.yy-d[v[i].yy])) << "\n";
            }
        }
    }
    else {

    }
    return 0;
}
/*
5
5 4 1 2 3
1 2
2 3
1 4
2 5
5
2 2 5 1
1 1 5
2 2 5 1
1 1 2
2 1 1 1
*/
/*
4
4 1 2 3
1 2
2 3
1 4
5
2 1 3 3
1 2 3
1 2 4
2 4 4 3
2 3 3 2
*/