HDU 6756

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T;
  cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    set<pair<int, int>> uniq;
    vector<int> A(n);
    cin >> A;
    for (int rep = 0; rep < m; ++rep) {
      int u, v;
      cin >> u >> v;
      --u; --v;
      if (u > v) swap(u, v);
      if (uniq.insert(make_pair(u, v)).second) {
        g[u].push_back(v);
        if (u != v)
          g[v].push_back(u);
      }
    }
    int B = sqrt(m), cnt = 0;
    if (B == 0) ++B;
    vector<int> id(n, -1);
    for (int i = 0; i < n; ++i)
      if (g[i].size() >= B)
        id[i] = cnt++;
    vector<vector<int>> bg(n);
    for (int i = 0; i < n; ++i) {
      for (int j : g[i])
        if (id[j] != -1)
          bg[i].push_back(id[j]);
    }
    vector<vector<int>> vs(cnt, vector<int>(n + 1)), bl(cnt, vector<int>(n / B + 1));
    set<int> al;
    for (int i = 0; i <= n; ++i) al.insert(i);
    auto ins = [&](int u) {
      if (A[u] > n) return;
      for (int j : bg[u])
        if (vs[j][A[u]]++ == 0)
          ++bl[j][A[u] / B];
    };
    auto ers = [&](int u) {
      if (A[u] > n) return;
      for (int j : bg[u])
        if (--vs[j][A[u]] == 0)
          --bl[j][A[u] / B];
    };
    for (int i = 0; i < n; ++i) ins(i);
    auto qry = [&](int u) {
      if (id[u] != -1) {
        int ret = 0;
        while (bl[id[u]][ret / B] == B) ret += B;
        while (vs[id[u]][ret]) ++ret;
        return ret;
      } else {
        vector<bool> vis(g[u].size() + 1);
        for (int j : g[u])
          if (A[j] < vis.size())
            vis[A[j]] = true;
        int ret = 0;
        while (vis[ret]) ++ret;
        return ret;
      }
    };
    int q;
    cin >> q;
    while (q--) {
      int opt, u;
      cin >> opt >> u;
      --u;
      if (opt == 1) {
        ers(u);
        cin >> A[u];
        ins(u);
      } else
        cout << qry(u) << '\n';
    }
  }

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}