#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long

using namespace ::std;

typedef struct
{
    int q;
    int l, r, x;
} Query;

void build(vector<int> &a, vector<int> &t, int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v] == a[tl];
    }
    else
    {
        int tm = (tl + tr) / 2;
        build(a, t, v * 2, tl, tm);
        build(a, t, v * 2 + 1, tm + 1, tr);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}

int getMax(vector<int> &t, int v, int tl, int tr, int l, int r)
{
    if (l > r)
        return 0;
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return max(getMax(t, v * 2, tl, tm, l, min(r, tm)), getMax(t, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}

void updateTree(vector<int> &t, int v, int tl, int tr, int pos, int val)
{
    if (tl == tr)
    {
        t[v] = val;
    }
    else
    {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
        {
            updateTree(t, v * 2, tl, tm, pos, val);
        }
        else
        {
            updateTree(t, v * 2 + 1, tm + 1, tr, pos, val);
        }
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i : a)
        cin >> i;
    int u, v;
    vector<vector<int>> adj(n);
    int mxad = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        adj[u - 1].push_back(v - 1);
        mxad = max(mxad, (int)adj[u - 1].size());
        adj[v - 1].push_back(u - 1);
        mxad = max(mxad, (int)adj[v - 1].size());
    }
    bool onlyx1 = true;
    int q;
    cin >> q;
    vector<Query> qs(q);
    for (auto &i : qs)
    {
        cin >> i.q;
        if (i.q == 1)
            cin >> i.l >> i.r;
        else
        {
            cin >> i.l >> i.r >> i.x;
        }
    }
    if (n <= 4000 && q <= 4000)
    {
        vector<vector<int>> dists(n, vector<int>(n, 0));
        for (int i = 0; i < n; ++i)
        {
            queue<int> q;
            vector<bool> visited(n, false);
            q.push(i);
            visited[i] = true;
            while (!q.empty())
            {
                int s = q.front();
                q.pop();
                for (auto j = adj[s].begin(); j != adj[s].end(); ++j)
                {
                    if (!visited[*j])
                    {
                        dists[i][*j] = dists[i][s] + 1;
                        visited[*j] = true;
                        q.push(*j);
                    }
                }
            }
        }
        for (int i = 0; i < q; i++)
        {
            if (qs[i].q == 1)
            {
                int temp = a[qs[i].l - 1];
                a[qs[i].l - 1] = a[qs[i].r - 1];
                a[qs[i].r - 1] = temp;
            }
            else
            {
                int mx = -1;
                for (int j = qs[i].l; j <= qs[i].r; ++j)
                {
                    if (dists[qs[i].x - 1][a[j - 1] - 1] > mx)
                        mx = dists[qs[i].x - 1][a[j - 1] - 1];
                }
                cout << mx << endl;
            }
        }
    }
    else if (mxad <= 2)
    {
        vector<int> dist(n, 0);
        for (int i = 0; i < n; i++)
        {
            if (adj[i].size() == 1)
            {
                queue<int> q;
                vector<bool> visited(n, false);
                q.push(i);
                visited[i] = true;
                while (!q.empty())
                {
                    int s = q.front();
                    q.pop();
                    for (auto j = adj[s].begin(); j != adj[s].end(); ++j)
                    {
                        if (!visited[*j])
                        {
                            //dists[i][*j] = dists[i][s] + 1;
                            dist[*j] = dist[s] + 1;
                            visited[*j] = true;
                            q.push(*j);
                        }
                    }
                }
                break;
            }
        }
        vector<int> adis(n, 0);
        for (int i = 0; i < n; ++i)
            adis[i] = dist[a[i] - 1];
    }
    else
    {
        vector<int> dist(n, 0);
        queue<int> qr;
        vector<bool> visited(n, false);
        qr.push(0);
        visited[0] = true;
        while (!qr.empty())
        {
            int s = qr.front();
            qr.pop();
            for (auto j = adj[s].begin(); j != adj[s].end(); ++j)
            {
                if (!visited[*j])
                {
                    //dists[i][*j] = dists[i][s] + 1;
                    dist[*j] = dist[s] + 1;
                    visited[*j] = true;
                    qr.push(*j);
                }
            }
        }
        vector<int> adis(n);
        for(int i=0;i<n;++i) adis[i] = dist[a[i] - 1];
        vector<int> seqtree(4*n);
        build(adis, seqtree, 1, 0, n - 1);
        for(int i=0;i<q;++i){
            if(qs[i].q == 1){
                int val1 = adis[qs[i].l - 1], val2 = adis[qs[i].r - 1];
                updateTree(seqtree, 1, 0, n - 1, qs[i].r - 1, val1);
                updateTree(seqtree, 1, 0, n - 1, qs[i].l - 1, val2);
            } else {
                if(qs[i].x == 1){
                    cout << getMax(seqtree, 1, 0, n - 1, qs[i].l - 1, qs[i].r - 1) << endl;
                }
                else cout << 0 << endl;
            }
        }
    }
    return 0;
}