I. 不见
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
很多年后，我才意识到。

这种突如其来的"不见"，以及那永远没有答案的结果，便是她对我的报复。

最温柔却最残忍的报复。

——《不见》

即便如此，良依然希望找到满穗。

洛阳城附近有若干条河流，其中一些相互联通。

每个河流有各自的宽度，宽度大小与能否找到满穗有关。

1. 对于一个环流，其宽度由其组成的最大河流宽度决定。

2. 对于一个链流，其宽度由其组成的最小河流宽度决定。

良需要你帮他找到决定所有河流宽度的河流，并输出方案，那里很可能找到满穗。

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

你可以执行若干次操作，最终使得整张图缩成一个点，每次操作选择以下两种操作的其中一种：

1. 选择一个简单环$$$^{\text{∗}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最大权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。

2. 选择一条链$$$^{\text{†}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最小权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。

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

请你找到在图缩成一个点后，能保留的最大权值，并输出一种操作方案，且操作次数不超过 $$$n$$$ 次。

如果存在多种合法方案，输出任意一种。

本题为 $$$\text{M}$$$ 题的 $$$\text{std}$$$ 程序。

$$$^{\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$$$），表示点权。

保证点权之间互不相同。

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

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

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

Output

对于每组测试数据：

第一行输出一个正整数，表示保留的最大权值。

第二行输出一个整数，表示操作次数 $$$k$$$。

接下来 $$$k$$$ 行，每行输出若干个数字。

第 $$$i$$$ 行第一个整数表示操作方式，第二个该次操作选择的节点数量 $$$l$$$。

接下来 $$$l$$$ 个数字，表示该次操作选择的节点序列 $$$p_1, p_2, \cdots,p_l$$$，其中任意 $$$i\ne j$$$ 均满足 $$$p_i \ne p_j$$$。

对于正整数 $$$i$$$（$$$1\le i \lt l$$$），在 $$$p_i$$$ 与 $$$p_{i+1}$$$ 均存在一条边。

若为操作 $$$1$$$，额外要求 $$$p_1$$$ 与 $$$p_l$$$ 之间存在一条边。

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