#include <bits/stdc++.h>

#define pb push_back
#define MAXN 80010

using namespace std;

int n, p[MAXN];
int q, o[MAXN], a[MAXN], b[MAXN], x[MAXN];

vector<int> graph[MAXN];
int dist[MAXN];

void dfs(int u) {

    for(int v: graph[u]) {
        if(dist[v] == -1) {
            dist[v] = dist[u] + 1;
            dfs(v);
        }
    }
}

int pos[MAXN];

pair<int, int> st[4 * MAXN];

void construct(int i, int l, int r) {

    if(l == r) {
        st[i] = {pos[p[l]], pos[p[l]]};
        return;
    }

    int mid = (l + r) / 2;
    construct(2 * i + 1, l, mid);
    construct(2 * i + 2, mid + 1, r);
    st[i] = {min(st[2 * i + 1].first, st[2 * i + 2].first), max(st[2 * i + 1].second, st[2 * i + 2].second)};
}

void upd(int i, int l, int r, int x, int sett) {

    if(x < l || r < x)
        return;
    if(l == r) {
        st[i] = {sett, sett};
        return;
    }
    
    int mid = (l + r) / 2;
    upd(2 * i + 1, l, mid, x, sett);
    upd(2 * i + 2, mid + 1, r, x, sett);
    st[i] = {min(st[2 * i + 1].first, st[2 * i + 2].first), max(st[2 * i + 1].second, st[2 * i + 2].second)};
}

pair<int, int> get(int i, int l, int r, int L, int R) {

    if(R < l || r < L)
        return {INT_MAX, INT_MIN};
    if(L <= l && r <= R)
        return st[i];
    
    int mid = (l + r) / 2;
    auto x = get(2 * i + 1, l, mid, L, R),
        y = get(2 * i + 2, mid + 1, r, L, R);
    return {min(x.first, y.first), max(x.second, y.second)};
}

void test2() {

    int u;
    for(int i = 0; i < n; i++) {
        if(graph[i].size() == 1) {
            u = i;
            break;
        }
    }

    int br = 0, parent = -1;
    pos[u] = br++;
    while(br < n) {
        for(int v: graph[u]) {
            if(v != parent) {
                parent = u;
                u = v;
                break;
            }
        }
        pos[u] = br++;
    }

    construct(0, 0, n - 1);
    for(int i = 0; i < q; i++) {
        if(o[i] == 1) {
            int t = p[b[i]];
            p[b[i]] = p[a[i]];
            p[a[i]] = t;

            upd(0, 0, n - 1, a[i], pos[p[a[i]]]);
            upd(0, 0, n - 1, b[i], pos[p[b[i]]]);
            continue;
        }

        auto k = get(0, 0, n - 1, a[i], b[i]);
        cout << max(abs(k.first - pos[x[i]]), abs(k.second - pos[x[i]])) << endl;
    }
}

int st1[4 * MAXN];

void construct1(int i, int l, int r) {

    if(l == r) {
        st1[i] = dist[p[l]];
        return;
    }

    int mid = (l + r) / 2;
    construct1(2 * i + 1, l, mid);
    construct1(2 * i + 2, mid + 1, r);
    st1[i] = max(st1[2 * i + 1], st1[2 * i + 2]);
}

void upd1(int i, int l, int r, int x, int sett) {

    if(x < l || r < x)
        return;
    if(l == r) {
        st1[i] = sett;
        return;
    }
    
    int mid = (l + r) / 2;
    upd1(2 * i + 1, l, mid, x, sett);
    upd1(2 * i + 2, mid + 1, r, x, sett);
    st1[i] = max(st1[2 * i + 1], st1[2 * i + 2]);
}

int get1(int i, int l, int r, int L, int R) {

    if(R < l || r < L)
        return INT_MIN;
    if(L <= l && r <= R)
        return st1[i];
    
    int mid = (l + r) / 2;
    return max(get1(2 * i + 1, l, mid, L, R), get1(2 * i + 2, mid + 1, r, L, R));
}

void test3() {

    for(int i = 0; i < n; i++)
        dist[i] = -1;
    dist[0] = 0;
    dfs(0);

    construct1(0, 0, n - 1);
    for(int i = 0; i < q; i++) {
        if(o[i] == 1) {
            int t = p[b[i]];
            p[b[i]] = p[a[i]];
            p[a[i]] = t;

            upd1(0, 0, n - 1, a[i], dist[p[a[i]]]);
            upd1(0, 0, n - 1, b[i], dist[p[b[i]]]);
            continue;
        }

        cout << get1(0, 0, n - 1, a[i], b[i]) << endl;
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }

    bool tst2 = true;
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;

        graph[u].pb(v);
        graph[v].pb(u);

        if(graph[u].size() > 2 || graph[v].size() > 2)
            tst2 = false;
    }

    cin >> q;
    bool tst3 = true;
    for(int i = 0; i < q; i++) {
        cin >> o[i] >> a[i] >> b[i];
        a[i]--; b[i]--;

        if(o[i] == 2) {
            cin >> x[i];
            x[i]--;

            if(x[i] != 0)
                tst3 = false;
        } else if(p[a[i]] == 0 || p[b[i]] == 0)
            tst3 = false;
    }

    if(tst2) {
        test2();
        return 0;
    }
    if(tst3) {
        test3();
        return 0;
    }

    for(int i = 0; i < n; i++) {
        if(o[i] == 1) {
            int t = p[b[i]];
            p[b[i]] = p[a[i]];
            p[a[i]] = t;
            continue;
        }

        for(int j = 0; j < n; j++)
            dist[j] = -1;
        dist[x[i]] = 0;
        dfs(x[i]);

        int ans = INT_MIN;
        for(int j = a[i]; j <= b[i]; j++)
            ans = max(ans, dist[p[j]]);
        cout << ans << endl;
    }
    return 0;
}