#include <bits/stdc++.h>

using namespace std;

#define pii pair<int,int>
#define ll long long
#define s second
#define f first

ll n, q, t  , x, y, l, r, a, b, p[80005], d[80005], st[320005];
vector<int> g[80005];

void dfs(int v, int p){
  if(p == -1){d[v] = 0;}
  else{d[v] = d[p] + 1;}
  for(auto u : g[v]){
    if(u == p){continue;}
    dfs(u, v);
  }
}

void build(int v, int l, int r){
  cout << v << " " << l + 1 << " " << r + 1 << " " << p[l] + 1 << " " << p[r] + 1 << endl;
  if(l == r){
    cout << l + 1 << " " << p[l] + 1 << " " << d[p[l]] << endl;
    st[v] = d[p[l]];
    return;
  }
  int mid = (l + r) / 2;
  build(2 * v, l, mid);
  build(2 * v + 1, mid + 1, r);
  st[v] = max(st[2 * v], st[2 * v + 1]);
}

int maxx(int v, int l, int r, int tl, int tr){
  //cout << l + 1 << " " << r + 1 << " " << st[v] << endl;
  if(l > tr || r < tl || l > r){return -1;}
  //cout << l + 1 << " " << r + 1 << " " << st[v] << endl;
  if(tl <= l && r <= tr){return st[v];}
  int mid = (l + r) / 2;
  return max(maxx(2 * v, l, mid, tl, tr), maxx(2 * v + 1, mid + 1, r, tl, tr));
}

void update(int v, int idx, int val, int l, int r){
  if(l == r){st[v] = val; return;}
  int mid = (l + r) / 2;
  if(idx <= mid){update(2 * v, idx, val, l, mid);}
  else{update(2 * v + 1, idx, val, mid + 1, r);}
  st[v] = max(st[2 * v], st[2 * v + 1]);
}

void Q1(){
  cin >> a >> b;
  --a; --b;
  swap(p[a], p[b]);
  update(1, b, d[p[b]], 0, n - 1);
  update(1, a, d[p[a]], 0, n - 1);
}

void Q2(){
  cin >> x >> y >> a;
  --x; --y;
  cout << maxx(1, 0, n - 1, x, y) << endl;
}

void q1(){
  cin >> a >> b;
  --a; --b;
  swap(p[a], p[b]);
}

void q2(){
  cin >> x >> y >> a;
  --x; --y; --a;
  dfs(a, -1);
  ll mx = 0;
  for(int i = x; i <= y; ++i){
    mx = max(d[p[i]], mx);
  }
  cout << mx << endl;
}

int main(){
  cin >> n;
  for(int i = 0; i < n; ++i){cin >> p[i]; --p[i];}
  for(int i = 0; i < n - 1; ++i){
    cin >> x >> y;
    --x; --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  cin >> q;
  while(q--){
    cin >> t;
    if(t == 1){q1();}
    else{q2();}
  }
  /*dfs(0, -1);
  build(1, 0, n - 1);
  for(int i = 0; i <= 2 * n; ++i){cout << st[i] << " ";}
  cout << endl;
  cin >> q;
  while(q--){
    cin >> t;
    if(t == 1){Q1();}
    else{Q2();}
  }*/
  return 0;
}