#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int mod=998244353;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second

void add(int &x,int y){x=(x+y>=mod)?(x+y-mod):x+y;}
int qpow(int x,int y){int ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=1;}return ret;}
const int N=3e5+5;

int n,m,k,c[N],col[N],fa[N],vis[N],ans,ret;
vector<int>e[N];
pii f[N];
void solve(){
	cin>>n>>m>>k;
	rep(i,1,n)cin>>c[i];
	for(int i=1,u,v;i<=m;i++)cin>>u>>v,e[u].pb(v),e[v].pb(u);
	rep(i,1,n)f[i]=mp(c[i],i),fa[i]=0,vis[i]=0,col[i]=0;
	sort(f+1,f+n+1);
	ans=ret=0;
	rep(t,1,n){
		int u=f[t].se;
		int currcol=1;
		for(int v:e[u])if(vis[v]){
			if(col[v]>=currcol){
				currcol=col[v]+1;fa[u]=v;
			}
		}
		vis[u]=1;
		col[u]=currcol;
		if(ans<currcol){
			ans=currcol;
			ret=u;
		}
	}
	printf("%d ",ans);
	rep(i,1,n)printf("%d ",col[i]);puts("");
	while(ret>0){
		printf("%d ",ret);
		ret=fa[ret];
	}
	puts("");
	rep(i,1,n)e[i].clear();
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int _;cin>>_;while(_--)solve();
	return 0;
}