思路：根号分治，若一个点度数大于阀值就开树状数组，小于就暴力修改。
查询就是二分。
已经用了快读，开了O2，可是还是T。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define cerr ((ostream) 0)
#define endl '\n'
#define debug(x) cerr << #x << " = " << x << endl
#define rep(i, a, b) for (register int i = (a); i <= (b); i++)
#define per(i, a, b) for (register int i = (a); i >= (b); i--)
#define gn(u, v) for (int v : G.G[u])
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define tomin(x, y) ((x) = min((x), (y)))
#define tomax(x, y) ((x) = max((x), (y)))
#define ck(mask, i) (((mask) >> (i)) & 1)
#define pq priority_queue
#define FLG (cerr << "Alive!" << endl);
constexpr int MAXN = 1e5+5;
// #define DEBUG 1 // 调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
char gc() {
#if DEBUG // 调试，可显示字符
return getchar();
#endif
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? ' ' : *p1++;
}
bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
template <class T>
void read(T &x) {
double tmp = 1;
bool sign = false;
x = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
if (ch == '.')
for (ch = gc(); isdigit(ch); ch = gc())
tmp /= 10.0, x += tmp * (ch - '0');
if (sign) x = -x;
}
void read(char *s) {
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
}
void read(char &c) { for (c = gc(); blank(c); c = gc()); }
void push(const char &c) {
#if DEBUG // 调试，可显示字符
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <class T>
void write(T x) {
if (x < 0) x = -x, push('-'); // 负数输出
static T sta[35];
T top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
template <class T>
void write(T x, char lastChar) {
write(x), push(lastChar);
}
} io;
struct Fenwick {
vi c, cnt;
inline int lowbit(int x) {
return x & (-x);
}
inline int sum(int x) {
if (x >= sz(c)) x = sz(c) - 1;
int s = 0;
for (int i = x; i >= 1; i -= lowbit(i))
s += c[i];
return s;
}
inline void add(int x, int v) {
if (x >= sz(c)) return;
bool bb = cnt[x];
cnt[x] += v;
if (bb ^ (!!cnt[x])) {
for (int i = x; i < sz(c); i += lowbit(i))
c[i] += v;
}
}
Fenwick() { }
Fenwick(int n) {
c.resize(n + 1, 0);
cnt.resize(n + 1, 0);
}
};
struct Edge {
int nxt, v;
} e[MAXN << 1], f[MAXN << 1];
int h[MAXN], g[MAXN], tot, tot2;
inline void init() {
memset(h, 0xff, sizeof h);
memset(g, 0xff, sizeof g);
tot = 0;
tot2 = 0;
}
inline void clear() {
memset(h, 0xff, sizeof(int) * (tot + 2));
memset(g, 0xff, sizeof(int) * (tot2 + 2));
tot = tot2 = 0;
}
inline void add(int u, int v) {
e[tot] = {h[u], v};
h[u] = tot++;
}
inline void add2(int u, int v) {
f[tot2] = {g[u], v};
g[u] = tot2++;
}
inline void add_edge(int u, int v) {
add(u, v);
add(v, u);
}
inline void add_edge2(int u, int v) {
add2(u, v);
add2(v, u);
}
int n, m;
int a[MAXN], d[MAXN];
bool big[MAXN];
Fenwick fwk[MAXN];
bool mex[MAXN];
inline void work() {
rep(i, 1, n) {
big[i] = false;
}
clear();
io.read(n);
io.read(m);
int BLOCK = sqrt(n);
rep(i, 1, n)
io.read(a[i]), a[i]++;
rep(i, 1, m) {
int u, v;
io.read(u);
io.read(v);
add_edge(u, v);
d[u]++;
d[v]++;
}
// rep(i, 1, n) {
// for (int x : G[i])
// cerr << x << " ";
// cerr << endl;
// }
rep(i, 1, n) {
if (d[i] > BLOCK) {
big[i] = true;
fwk[i] = Fenwick(d[i] + 2);
for (int it = h[i]; ~it; it = e[it].nxt) {
add2(e[it].v, i);
// cerr << u << " " << i << endl;
}
}
}
// rep(i, 1, n) {
// cerr << i << ": " << endl;
// for (int v : imp[i]) {
// cerr << v << " ";
// }
// cerr << endl;
// }
rep(i, 1, n) {
for (int it = g[i]; ~it; it = f[it].nxt) {
fwk[f[it].v].add(a[i], 1);
}
}
int q;
io.read(q);
rep(i, 1, q) {
int opt, u, x;
io.read(opt);
io.read(u);
if (opt == 1) {
io.read(x);
x++;
for (int it = g[u]; ~it; it = f[it].nxt) {
fwk[f[it].v].add(a[u], -1);
fwk[f[it].v].add(x, 1);
}
a[u] = x;
} else if (opt == 2) {
if (big[u]) {
int ans = 0;
// for (int j = 1; j <= 114514; j++) {
// cerr << fwk[u].sum(j) << " ";
// if (fwk[u].sum(j) != j) {
// ans = j - 1;
// break;
// }
// }
// cerr << endl;
for (int j = (1 << 20); j; j >>= 1) {
ans += j;
if (ans != fwk[u].sum(ans))
ans -= j;
}
io.write(ans, '\n');
} else {
for (int it = h[u]; ~it; it = e[it].nxt) {
// cerr << a[v] << " ";
mex[a[e[it].v]] = true;
}
// cerr << endl;
int ans = 0;
while (mex[ans]) ans++;
io.write(ans, '\n');
for (int it = h[u]; ~it; it = e[it].nxt) {
// cerr << a[v] << " ";
mex[a[e[it].v]] = false;
}
}
}
}
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
init();
int t;
io.read(t);
while (t--) work();
return 0;
}