// #pragma GCC optimize("Ofast")
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
// #define getchar() (frS==frT&&(frT=(frS=frBB)+fread(frBB,1,1<<15,stdin),frS==frT)?EOF:*frS++)
char frBB[1<<15],*frS=frBB,*frT=frBB;
inline long read(){
  long ans=0,f=1;char chr=getchar();
  while(!isdigit(chr)){if(chr=='-')f=-1;chr=getchar();}
  while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
  return ans*f;
}
inline void cmax(int &a,int b){a<b?a=b:0;}
inline void cmin(int &a,int b){a>b?a=b:0;}
const int M = 3e5+5;
int n,m,k,T,ans,col[M],dp[M];
vector<int>g[M],Ans;
// auto dfs = [=](int x){
//     for(int y:g[x])
//         dfs(y),cmax(dp[x],dp[y]+1);
// }
void dfs(int x){
    for(int y:g[x])
        dfs(y),cmax(dp[x],dp[y]+1);
}
void dfs1(int x){
    Ans.emplace_back(x);
    for(int y:g[x])
        if(dp[y]==dp[x]-1){
            dfs1(y);
            break;
        }
}
signed main(){
    T=read();
    while(T--){
        n=read(),m=read(),k=read();Ans.clear();
        for(int i=1;i<=n;i++)col[i]=read(),dp[i]=0,g[i].clear();
        for(int i=1,x,y;i<=m;i++){
            x=read(),y=read();
            if(col[x]<col[y])swap(x,y);
            g[x].push_back(y);
        }
        for(int i=1;i<=n;i++)
            if(!dp[i])dfs(i);
        int S,ans=0;
        for(int i=1;i<=n;i++)
            if(dp[i]>ans)
                ans=dp[i],S=i;
        dfs1(S);
        cout<<ans+1<<" ";
        for(int i=1;i<=n;i++)cout<<dp[i]+1<<" ";cout<<endl;
        for(auto x:Ans)cout<<x<<" ";cout<<endl;
    }
    return 0;
}