Given an undirected graph G=(V,E). All vertices are numbered from 1 to N. And every vertex u has a value of Au. Let Su={Av│(u,v)∈E}. Also, F(u) equals MEX(minimum excludant) value of Su. A MEX value of a set is the smallest non-negative integer which doesn’t exist in the set.
There are two types of queries.
Type 1: 1 u x – Change Au to x (0≤x≤109). Type 2: 2 u – Calculate the value of F(u).
For each query of type 2, you should answer the query.
输入格式
The first line of input contains a single integer T (1≤T≤10) denoting the number of test cases. Each test case begins with a single line containing two integers n (1≤n≤105), m (1≤m≤105) denoting the number of vertices and number of edges in the given graph.
The next line contains n integers and ith of them is a value of Ai (0≤Ai≤109).
The next m lines contain edges of the graph. Every line contains two integers u, v meaning there exist an edge between vertex u and v.
The next line contains a single integer q (1≤q≤105) denoting the number of queries.
The next q lines contain queries described in the description.
输出格式
For each query of type 2, output the value of F(u) in a single line.