#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int p[N];
int degree[N];
int depth[N];
int vals[N];
bool vis[N];
vector<int> graph[N];

int segmin[2 * N];
int segmax[2 * N];

void buildmin(int n) {
    for (int i = 0; i < n; i++) {
        segmin[i + n] = vals[i];
    }
    for (int i = n - 1; i > 0; i--) {
        segmin[i] = min(segmin[2 * i], segmin[2 * i + 1]);
    }
}

void updatemin(int pos, int val, int n) {
    pos += n;
    segmin[pos] = val;
    while (pos > 1) {
        pos /= 2;
        segmin[pos] = min(segmin[2 * pos], segmin[2 * pos + 1]);
    }
}

int rminq(int l, int r, int n) {
    l += n;
    r += n;
    int mn = 1e9;
    while (l < r) {
        if (r % 2 == 1) {
            mn = min(mn, segmin[--r]);
        }
        if (l % 2 == 1) {
            mn = min(mn, segmin[l++]);
        }
        l /= 2;
        r /= 2;
    }
    return mn;
}

void buildmax(int n) {
    for (int i = 0; i < n; i++) {
        segmax[i + n] = vals[i];
    }
    for (int i = n - 1; i > 0; i--) {
        segmax[i] = max(segmax[2 * i], segmax[2 * i + 1]);
    }
}

void updatemax(int pos, int val, int n) {
    pos += n;
    segmax[pos] = val;
    while (pos > 1) {
        pos /= 2;
        segmax[pos] = max(segmax[2 * pos], segmax[2 * pos + 1]);
    }
}

int rmaxq(int l, int r, int n) {
    l += n;
    r += n;
    int mx = 0;
    while (l < r) {
        if (r % 2 == 1) {
            mx = max(mx, segmax[--r]);
        }
        if (l % 2 == 1) {
            mx = max(mx, segmax[l++]);
        }
        l /= 2;
        r /= 2;
    }
    return mx;
}


void dfs(int v) {
    vis[v] = true;
    for (auto x : graph[v]) {
        if (!vis[x]) {
            depth[x] = depth[v] + 1;
            dfs(x);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    bool f = true;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
        degree[a]++;
        degree[b]++;
        if (degree[a] > 2 || degree[b] > 2) {
            f = false;
        }
    }

    int root = 0;

    if (f) {
        for (int i = 1; i < n; i++) {
            if (degree[i] == 1) {
                root = i;
            }
        }
    }
    dfs(root);
    for (int i = 0; i < n; i++) {
        vals[i] = depth[p[i]];
    }
    buildmin(n);
    buildmax(n);
    int q;
    cin >> q;

    if (n <= 4000 && q <= 4000) {
        for (int i = 0; i < q; i++) {
            int t;
            cin >> t;
            if (t == 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--;
                for (int j = 0; j < n; j++) {
                    vis[j] = false;
                }
                depth[x] = 0;
                dfs(x);
                int ans = 0;
                for (int j = l; j <= r; j++) {
                    ans = max(ans, depth[p[j]]);
                }
                cout << ans << endl;
            }
        }
        return 0;
    }
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            int u = p[a];
            int v = p[b];
            swap(p[a], p[b]);
            vals[a] = depth[v];
            vals[b] = depth[u];
            updatemin(a, depth[v], n);
            updatemin(b, depth[u], n);
            updatemax(a, depth[v], n);
            updatemax(b, depth[u], n);
        } else {
            int l, r, x, ans;
            cin >> l >> r >> x;
            l--, r--, x--;
            if (!f) {
                ans = rmaxq(l, r + 1, n);
            } else
                ans = max(rmaxq(l, r + 1, n) - depth[x], depth[x] - rminq(l, r + 1, n));
            cout << ans << endl;
        }
    }


    return 0;
}