#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 200001;
const int inf = 1e9 + 7;
int a[N], b[N];
int dp1[4001][4001];
int dp2inv[N], dp3[N];
int poz[N], part[N];
pair<int, int> seg[4 * N];
vector<int> graph[N];
vector<int> query[N];
int maxver;
int ind = 0;

void dfs(int u, int u1, int br, int p) {
    if (p <= 4000 && u <= 4000)
        dp1[p][u] = br;
    else if (p == 4001) {
        dp2inv[u] = ind++;
    }
    for (auto i = graph[u].begin(); i != graph[u].end(); i++) {
        if (graph[u].size() == 1)
            maxver = u;
        if (*i == u1)
            continue;
        dfs(*i, u, br + 1, p);
    }
}

void rec(int u) {
    seg[u] = {min(seg[u * 2 + 1].first, seg[u * 2 + 2].first), max(seg[u * 2 + 1].second, seg[u * 2 + 2].second)};
}

void build(int u, int l, int r, bool p) {
    if (l == r) {
        if (!p)
            seg[u] = {dp2inv[a[l]], dp2inv[a[l]]};
        else
            seg[u] = {dp3[a[l]], dp3[a[l]]};
        return;
    }
    int mid = l + r >> 1;
    build(u * 2 + 1, l, mid, p);
    build(u * 2 + 2, mid + 1, r, p);
    rec(u);
}

void change(int u, int l, int r, int x, int y, bool p) {
    if (l == r) {
        if (!p)
            seg[u] = {dp2inv[y], dp2inv[y]};
        else
            seg[u] = {dp3[y], dp3[y]};
        return;
    }
    int mid = l + r >> 1;
    if (mid >= x)
        change(u * 2 + 1, l, mid, x, y, p);
    else
        change(u * 2 + 2, mid + 1, r, x, y, p);
    rec(u);
}

pair<int, int> nadji(int u, int l, int r, int L, int R) {
    if (l > R || r < L)
        return {inf, -1};
    if (l >= L && r <= R) {
        return seg[u];
    }
    int mid = l + r >> 1;
    pair<int, int> pr = nadji(u * 2 + 1, l, mid, L, R), dr = nadji(u * 2 + 2, mid + 1, r, L, R);
    return {min(pr.first, dr.first), max(pr.second, dr.second)};
}

void solve() {
    int n;
    cin >> n;
    int maxv = 0;
    bool check = true;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        poz[a[i]] = i;
    }
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
        maxv = max(maxv, (int)max(graph[x].size(), graph[y].size()));
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x, l, r, u;
        cin >> x >> l >> r;
        query[i].push_back(x), query[i].push_back(l - 1), query[i].push_back(r - 1);
        if (x == 2) {
            cin >> u;
            query[i].push_back(u - 1);
            if (u != 1) {
                check = false;
            }
            continue;
        }
        if (a[l-1] == 0 || a[r-1] == 0)
            check = false;
    }
    if (q < 4001 && n < 4001) {
        for (int i = 0; i < n; i++)
            dfs(i, -1, 0, i);
        for (int i = 0; i < q; i++) {
            int x = query[i][0], l = query[i][1], r = query[i][2], u;
            if (x == 2) {
                u = query[i][3];
                int maxx = 0;
                for (int j = l; j <= r; j++) {
                    maxx = max(maxx, dp1[u][a[j]]);
                }
                cout << maxx << endl;
                continue;
            }
            swap(a[l], a[r]);
        }
        return;
    }
    if (maxv <= 2) {
        dfs(0, -1, 0, 4002);
        dfs(maxver, -1, 0, 4001);
        build(0, 0, n - 1, 0);
        for (int i = 0; i < q; i++) {
            int x = query[i][0], l = query[i][1], r = query[i][2], u;
            if (x == 2) {
                pair<int, int>res = nadji(0, 0, n - 1, l, r);
                cout << max(abs(res.first - dp2inv[u]), abs(res.second - dp2inv[u])) << endl;
                continue;
            }
            change(0, 0, n - 1, l, a[r], 0);
            change(0, 0, n - 1, r, a[l], 0);
        }
        return;
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}