#include <bits/stdc++.h>
template <class T>
using V = std::vector<T>;
template <class T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class T>
void chkmin(T &x, const T &y) {
  if (x > y) x = y;
}
using ll = long long;
using ull = unsigned long long;
using bset = std::bitset<100001>;

std::array<bset, 100001> bs;

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  freopen("recall.in", "r", stdin);
  freopen("recall.out", "w", stdout);
  int c, t;
  std::cin >> c >> t;
  if (c >= 6 && c <= 9) {
    while (t--) {
      int n, m, q;
      std::cin >> n >> m >> q;
      bs.fill({});
      V<int> a(n + 1), b(n + 1), aw(n + 1), bw(n + 1);
      V<V<int>> g(n + 1);
      for (int i = 1; i <= m; i++) {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
      }
      for (int i = 1; i <= n; i++) std::cin >> a[i];
      for (int i = 1; i <= n; i++) std::cin >> b[i], b[i] = n - b[i] + 1;
      for (int i = 1; i <= n; i++) aw[a[i]] = b[i];
      for (int i = n; i >= 1; i--) {
        bs[i][b[i]] = 1;
        for (int v : g[i]) bs[i] |= bs[v];
      }
      V<std::array<int, 5>> que;
      V<std::array<int, 3>> swp; 
      V<int> ans(q);
      for (int i = 0; i < q; i++) {
        int o;
        std::cin >> o;
        if (o == 3) {
          int x, l, r;
          std::cin >> x >> l >> r;
          que.push_back({swp.size(), l, r, x, i});
        } else {
          int x, y;
          std::cin >> x >> y;
          swp.push_back({o, x, y});
          ans[i] = -1;
        }
      }
      std::sort(que.begin(), que.end(), [&](auto &a, auto &b) -> bool {
        if (a[0] / 2000 != b[0] / 2000) return a[0] < b[0];
        if (a[1] / 340 != b[1] / 340) return a[1] < b[1];
        return (a[2] < b[2]) ^ ((a[1] / 340) & 1);  
      });
      bset cur;
      int l = 1, r = 0, t = 0;
      for (auto qv : que) {
        int qt = qv[0], ql = qv[1], qr = qv[2], qx = qv[3], qid = qv[4];
        while (l > ql) cur[aw[--l]] = 1;
        while (r < qr) cur[aw[++r]] = 1;
        while (l < ql) cur[aw[l++]] = 0;
        while (r > qr) cur[aw[r--]] = 0;
        auto swap = [&](int o, int x, int y) {
          if (o == 2) std::swap(b[x], b[y]), std::swap(bw[b[x]], bw[b[y]]);
          else {
            std::swap(a[x], a[y]), std::swap(aw[a[x]], aw[a[y]]);
            if (cur[b[x]] != cur[b[y]]) cur[b[x]] = cur[b[y]], cur[b[y]] = cur[b[x]] ^ 1;
          }
        };
        while (t < qt) swap(swp[t][0], swp[t][1], swp[t][2]), ++t;
        while (t > qt) --t, swap(swp[t][0], swp[t][1], swp[t][2]);
        auto tmp = bs[qx] & cur;
        ans[qid] = n - tmp._Find_first() + 1;
        if (ans[qid] < 0) ans[qid] = 0;
      }
      for (int i : ans) if (i != -1) std::cout << i << '\n';    
    }
  } else {
    while (t--) {
    int n, m, q;
    std::cin >> n >> m >> q;
    bs.fill({});
    V<int> a(n + 1), b(n + 1), aw(n + 1), bw(n + 1);
    V<V<int>> g(n + 1);
    for (int i = 1; i <= m; i++) {
      int u, v;
      std::cin >> u >> v;
      g[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) std::cin >> a[i], aw[a[i]] = i;
    for (int i = 1; i <= n; i++) std::cin >> b[i], bw[b[i]] = i;
    for (int i = n; i >= 1; i--) {
      bs[i][i] = 1;
      for (int v : g[i]) bs[i] |= bs[v];
    }
    V<std::array<int, 5>> que;
    V<std::array<int, 3>> swp; 
    V<int> ans(q);
    for (int i = 0; i < q; i++) {
      int o;
      std::cin >> o;
      if (o == 3) {
        int x, l, r;
        std::cin >> x >> l >> r;
        que.push_back({swp.size(), l, r, x, i});
      } else {
        int x, y;
        std::cin >> x >> y;
        swp.push_back({o, x, y});
        ans[i] = -1;
      }
    }
    std::sort(que.begin(), que.end(), [&](auto &a, auto &b) -> bool {
      if (a[0] / 2000 != b[0] / 2000) return a[0] < b[0];
      if (a[1] / 340 != b[1] / 340) return a[1] < b[1];
      return (a[2] < b[2]) ^ ((a[1] / 340) & 1);  
    });
    bset cur;
    int l = 1, r = 0, t = 0;
    for (auto qv : que) {
      int qt = qv[0], ql = qv[1], qr = qv[2], qx = qv[3], qid = qv[4];
      while (l > ql) cur[aw[--l]] = 1;
      while (r < qr) cur[aw[++r]] = 1;
      while (l < ql) cur[aw[l++]] = 0;
      while (r > qr) cur[aw[r--]] = 0;
      auto swap = [&](int o, int x, int y) {
        if (o == 2) std::swap(b[x], b[y]), std::swap(bw[b[x]], bw[b[y]]);
        else {
          std::swap(a[x], a[y]), std::swap(aw[a[x]], aw[a[y]]);
          if (cur[x] != cur[y]) cur[x] = cur[y], cur[y] = cur[x] ^ 1;
        }
      };
      while (t < qt) swap(swp[t][0], swp[t][1], swp[t][2]), ++t;
      while (t > qt) --t, swap(swp[t][0], swp[t][1], swp[t][2]);
      auto tmp = bs[qx] & cur;
      for (int i = n; i >= 1 && i >= n - 40000; i--) {
        if (tmp[bw[i]]) {
          ans[qid] = i;
          break;
        }
      }
      if (!ans[qid]) {
        for (int i = tmp._Find_first(); i < tmp.size(); i = tmp._Find_next(i))
          chkmax(ans[qid], b[i]);
      }
    }
    for (int i : ans) if (i != -1) std::cout << i << '\n';    
  }
  }
}