M. 同生
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
此时此刻，她还活着。

我能和她一起，看着她活着。

仅仅如此，对我而言便是最好的事了。

——《同生》

自此烟雨落金城，一人撑伞两人行。

九年之约，良穗相遇。

良已践行与满穗立下的湖畔之约，满穗再次宽限良，允许他实现最后的愿望。

就此，两人乘着小船，踏上了扬州之旅。

包括洛阳和扬州在内的若干个城镇由多条河流相连，且每个城镇有各自的发展水平值，船夫需要提前规划路线。

在船夫的规划有两种方式：

  • 选择若干个城镇，且这些城镇能组成一个简单环，保留被选择的城镇中发展程度值最大的城镇，其中原本未被选择城镇连接到被选择城镇的河流视为连接到最后保留的城镇。
  • 选择若干个城镇，且这些城镇能组成一个链，保留被选择的城镇中发展程度最小的城镇，其中原本未被选择城镇连接到被选择城镇的河流视为连接到最后保留的城镇。

现在给定船夫的操作方案，请你帮忙计算最后保留城镇的发展程度值，若操作不合法或操作后不为一个点，输出 -1。

形式化的：给定一张有 $$$n$$$ 个点的无向图，每个节点有一个权值 $$$a_i$$$。

给定一个操作序列，其中包含两种合法操作：

  • 选择一个点序列 $$$P$$$，其中任意两点不相同，且对于 $$$1\le i\le|P|$$$，均满足 $$$p_i$$$ 与 $$$p_{\left(i~\text{mod}~|P|\right)+1}$$$ 之间存在一条边，即这些点构成简单环$$$^{\text{∗}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最大权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。
  • 选择一个点序列 $$$P$$$，其中任意两点不相同，且对于 $$$1\le i \lt |P|$$$，均满足 $$$p_i$$$ 与 $$$p_{i+1}$$$ 之间存在一条边，即这些点构成一条链$$$^{\text{†}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最小权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。

其中，第 $$$i$$$ 次操作建立的新节点编号为 $$$n + i$$$。

请你计算操作后，在图缩成一个点后所保留的权值，若操作不合法或图不仅剩一点，输出 -1。

本题为 $$$\text{I}$$$ 题的 $$$\text{checker}$$$ 程序。

$$$^{\text{∗}}$$$一条至少包含三条边的闭合路径，其中除了起点和终点相同外，其余所有顶点均不重复，且所有边也不重复。

$$$^{\text{†}}$$$一条所有顶点都不重复的路径。

Input

有多组测试数据。

第一行输入一个正整数 $$$T$$$（$$$1\le T \le 10^3$$$），表示测试数据组数，对于每组测试数据：

第一行输入两个正整数 $$$n$$$，$$$m$$$（$$$1\le n \le 10^5$$$，$$$n-1\le m\le \min\left(\frac{n(n-1)}{2},10^6\right)$$$），分别表示图中点数量，边数量。

接下来一行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1\le a_i\le n$$$），表示第 $$$i$$$ 个点的点权。

保证点权之间互不相同。

接下来 $$$m$$$ 行，每行输入两个正整数 $$$u_i$$$，$$$v_i$$$（$$$1\le u_i,v_i\le n$$$，$$$u_i \ne v_i$$$），表示一条连接 $$$u_i$$$ 和 $$$v_i$$$ 的边。

保证给定的图为连通图，且不存在重边、自环。

接下来一行输入一个正整数 $$$q$$$（$$$1\le q\le n$$$），表示操作序列长度。

接下来 $$$q$$$ 行，第 $$$i$$$ 行输入若干个整数 $$$op$$$，$$$l$$$，$$$p_1,p_2,\cdots,p_l$$$（$$$1\le op\le2$$$，$$$1 \lt l\le n$$$，$$$1\le p_i\le 2\times n$$$），描述了操作方式和操作所选的点序列。

保证所有数据 $$$n$$$ 之和不超过 $$$10^5$$$，$$$m$$$ 之和不超过 $$$10^6$$$。

Output

对于每组测试数据：输出一行，包含一个整数，表示答案。

Example
Input
2
4 4
1 2 4 3
1 2
2 3
1 3
1 4
2
1 3 1 2 3
2 2 5 4
4 4
4 2 1 3
1 2
2 3
1 3
1 4
1
1 3 2 1 4
Output
3
-1