你有一个无向图，每个顶点被染成 $k$ 种颜色中的一种，且该图被正确地染成了 $k$ 种颜色，即任意一条边的两个端点颜色不同。

你的目标是找到该图的另一种（或者相同的）染色方案，使用 $x$ 种颜色，使得 $x \le k$，并且存在一条长度为 $x$ 的路径，该路径包含了所有 $x$ 种颜色。

题目保证一定有解。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 600\,000$)：测试用例的数量。

每个测试用例的第一行包含三个整数 $n, m$ 和 $k$：图的顶点数、边数以及你正在使用的颜色数量 ($1 \le n \le 300\,000; 0 \le m \le 300\,000; 1 \le k \le n$)。

下一行包含 $n$ 个空格分隔的整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le k$)：顶点的颜色。

题目保证给定的染色方案是正确的。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n; u \neq v$)：由边连接的顶点索引。

题目保证每个测试用例中图中没有重边。

题目保证所有测试用例的 $n + m$ 之和不超过 $600\,000$。

输出格式

对于每个测试用例，输出 $n + 1$ 个整数：$x$ ($1 \le x \le k$) 以及 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le x$)，表示新的染色方案。

该染色方案必须是正确的，即任意一条边的两个端点颜色不同。

此外，对于每个测试用例，在下一行输出 $x$ 个整数 $v_1, v_2, \dots, v_x$ ($1 \le v_i \le n$)，要求顶点 $v_i$ 和 $v_{i+1}$ 之间存在边，且所有顶点的颜色必须互不相同，即对于所有 $1 \le i < j \le x$，满足 $p_{v_i} \neq p_{v_j}$。

样例

样例输入 1

2
3 3 3
1 2 3
1 2
2 3
3 1
3 1 3
1 2 3
1 2

样例输出 1

3 3 2 1
1 2 3
2 2 1 1
1 2