题目描述

画师遥拿到了一张无向图，图中每个顶点已经被染成 $k$ 种颜色之一。当前染色是合法的，也就是说任意一条边的两个端点颜色都不同。

现在遥希望重新给这张图染色。你需要找到一个新的合法染色，使用 $x$ 种颜色，其中

同时，图中必须存在一条包含 $x$ 个顶点的路径

使得路径上的相邻顶点之间都有边，并且这 $x$ 个顶点在新染色中颜色两两不同。换句话说，这条路径正好展示出新染色中所有可能的颜色。

可以证明，在本题限制下一定存在答案。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

对于每个测试用例：

第一行包含三个整数 $n,m,k$，分别表示顶点数、边数和原本使用的颜色数。

第二行包含 $n$ 个整数

表示每个顶点的原颜色。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示顶点 $u$ 和 $v$ 之间有一条边。

输入保证原染色合法，且每个测试用例中不存在重边。

输出格式

对于每个测试用例，输出两行。

第一行输出 $n+1$ 个整数：

其中 $x$ 表示新染色使用的颜色数，$p_i$ 表示顶点 $i$ 的新颜色。需要满足 $1\le x\le k$ 且 $1\le p_i\le x$。

第二行输出 $x$ 个整数：

表示一条路径。需要满足每个 $v_i$ 是合法顶点编号，相邻顶点之间有边，并且路径上所有顶点的新颜色两两不同。

数据范围

• $1\le t\le 600000$；
• $1\le n\le 300000$；
• $0\le m\le 300000$；
• $1\le k\le n$；
• $1\le c_i\le k$；
• $1\le u,v\le n$，且 $u\ne v$；
• 所有测试用例的 $n+m$ 之和不超过 $600000$。

样例 1

输入

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

输出

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