1const itn maxn = 1e5 + 10;
2
3int n, m, w[maxn];
4struct star{int to, next;};
5
6int head[maxn], top = 0;
7int du[maxn], K;
8star edge[maxn << 1];
9void add(int u, int v){
10 edge[top].to = v;
11 edge[top].next = head[u];
12 head[u] = top++;
13}
14
15unordered_map<int, int> mp[maxn];
16unordered_map<int, int> conv;
17
18int c[700][maxn], bitcnt = 0, zero[maxn];
19void add(int id, int i, int x, int n){
20 while(i <= n){ c[id][i] += x; i += lowbit(i);}
21}
22int query(int id, int i){
23 int ans = 0;
24 while(i){ans += c[id][i]; i -= lowbit(i);} return ans;
25}
26
27void bitupdate(int u, int key, int op){
28 assert(conv.count(u) == 1);
29 int id = conv[u]; add(id, key, op, du[u]);
30}
31
32//将u节点的邻接权值key的数量 += op
33void update(int u, int key, int op){
34 if(key > du[u]) return;
35
36 //特判断0
37 if(key == 0){
38 zero[u] += op; return;
39 }
40
41 mp[u][key] += op;
42 // 1 - >0
43 if(mp[u][key] == 0){
44 bitupdate(u, key, -1);
45 mp[u].erase(key);
46 }
47 //0 -> 1
48 if(mp[u][key] == 1 && op == 1) bitupdate(u, key, 1);
49
50}
51
52//检查u节点的邻点中 权值x及其之前是否填满
53bool check(int u, int x){
54 if(x == 0){
55 if(zero[u] == 0) return 0;
56 return 1;
57 }
58 int cnt = query(conv[u], x);
59 return x == cnt;
60}
61
62int temp[maxn];
63int mex(int u){
64 if(du[u] < K){
65 for(int i = 0; i <= du[u]; i++) temp[i] = 0;
66 for(int i = head[u]; ~i; i = edge[i].next){
67 if(w[edge[i].to] > du[u]) continue;
68 temp[w[edge[i].to]] = 1;
69 }
70 for(int i = 0; i <= du[u]; i++) if(!temp[i]) return i;
71 return -1;
72 }
73 else{
74 if(zero[u] == 0) return 0;
75
76 int left = 0, right = du[u], middle;
77 while(left < right){
78 middle = (left + right) >> 1;
79 if(check(u, middle)) left = middle + 1;
80 else right = middle;
81 }
82 return left;
83 }
84}
85
86unordered_set<int> vec[maxn];
87
88struct NODE{
89 int x, y;
90 NODE(int _x, int _y){
91 x = min(_x, _y);
92 y = max(_x, _y);
93 }
94 bool operator <(const NODE &b)const{
95 if(x != b.x) return x < b.x;
96 else return y < b.y;
97 }
98};
99set<NODE> EDGE;
100
101int main(){
102// Fastin;
103 int t; scanf("%d", &t); while(t--){
104 clr(head, -1); top = 0; clr(du, 0); clr(zero, 0); bitcnt = 0;
105
106 n = read(); m = read();
107
108 for(int i = 1; i <= n; i++) mp[i].clear(); conv.clear();
109
110 K = sqrt(m);
111 for(int i = 1; i <= n; i++){
112 w[i] = read(); vec[i].clear();
113 }
114
115 EDGE.clear();
116 for(int i = 0; i < m; i++){
117 int u, v; u = read(); v = read();
118 EDGE.insert(NODE(u, v));
119 }
120 for(auto edge: EDGE){
121 if(edge.x != edge.y){
122 add(edge.x, edge.y); add(edge.y, edge.x);
123 du[edge.x]++; du[edge.y]++;
124 }
125 else{
126 add(edge.x, edge.y);
127 du[edge.x]++;
128 }
129 }
130 //只有O(sqrt(m))个点的度>= K = sqrt(m)
131 for(int i = 1; i <= n; i++) if(du[i] >= K){
132 memset(c[bitcnt], 0, sizeof (c[bitcnt]));
133 conv[i] = bitcnt++;
134 for(int j = head[i]; ~j; j = edge[j].next){
135 int to = edge[j].to; vec[to].insert(i);
136 update(i, w[to], 1);
137 }
138 }
139
140 int q; scanf("%d", &q); while(q--){
141 itn op, x, y; scanf("%d", &op);
142 if(op == 1){
143 x = read(); y = read();
144 //w[x] := y;
145 //v是所有的相邻大度点
146 for(auto v: vec[x]){
147 update(v, w[x], -1);
148 update(v, y, 1);
149 }
150 w[x] = y;
151 }
152 else{
153 x = read();
154 printf("%d\n", mex(x));
155 }
156 }
157 }
158 return 0;
159}
160