#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(i=a;i<b;++i) #define repi(i,a,b) for(int i=a;i<b;++i) #define F first #define S second #define mp(a,b) make_pair(a,b) #define pii pair<int,int> #define ppi pair<pii,int> #define ppp pair<pii,pii> #define vi vector<int> #define sc(a) scanf("%d",&a) #define pb(a) push_back(a) #define DEBUG2 int t; int n,m,k; unordered_set<int> kset; vector<int> e[100001]; vector<int> e2[100001]; int c[100001]; void inp() { repi(i,0,k) sc(c[i]); repi(i,0,k) kset.insert(c[i]); repi(i,0,m) { int x,y; sc(x); sc(y); if(x!=y) e[x].pb(y); } } bool ex[100001]; stack<int> dfss; void dfs1(int i) { #ifdef DEBUG1 printf("dfs1 : %d\n",i); #endif for(int x : e[i]) { if(!ex[x]) { ex[x] = true; dfs1(x); } } dfss.push(i); } int compo[100001]; int numc = 0; priority_queue<int, std::vector<int>, std::greater<int>> g2[100001]; set<int> e3[100001]; int indeg[100001]; void dfs2(int i, int comp) { #ifdef DEBUG1 printf("dfs2: %d, comp: %d\n",i,comp); #endif compo[i] = comp; if(kset.count(i)) { g2[comp].push(i); } for(int x: e2[i]) { if(!ex[x]) { ex[x] = true; dfs2(x,comp); } else if(compo[x] != comp && !e3[compo[x]].count(comp)) { e3[compo[x]].insert(comp); indeg[comp]++; } } } int comp = 0; void builddag() { comp = 0; repi(i,1,n+1) ex[i] = false; repi(i,1,n+1) if(!ex[i]) { ex[i] = true; dfs1(i); } repi(i,1,n+1) ex[i] = false; repi(i,1,n+1) for(int x : e[i]) e2[x].pb(i); while(!dfss.empty()) { if(ex[dfss.top()]) dfss.pop(); else { ex[dfss.top()] = true; dfs2(dfss.top(), comp++); dfss.pop(); } } numc = comp; } int chil[100001]; int nex[100001]; void dfslast(int i) { chil[i] = 0; for(int x: e3[i]) { if(!ex[x]) { ex[x] = true; dfslast(x); } if(chil[i] < chil[x]) { nex[i] = x; chil[i] = chil[x]; } chil[i] = max(chil[i],chil[x]); } chil[i] += (g2[i].size()>0); #ifdef DEBUG1 printf("dfslast: i: %d chil: %d\n",i,chil[i]); #endif } queue<int> ansq; void dfsone(int i) { #ifdef DEBUG1 printf("%d: dfsone: %d -> %d\n",t,i,nex[i]); #endif ansq.push(i); ex[i] = true; if(nex[i] != -1) dfsone(nex[i]); } void checkposs() { repi(i,0,comp) ex[i] = false; repi(i,0,comp) nex[i] = -1; repi(i,0,comp) { if(indeg[i] == 0) { ex[i] = true; dfslast(i); } } int maxx = -1; int maxel = -1; repi(i,0,comp) { if(chil[i]>maxx) { maxx = chil[i]; maxel = i; } } repi(i,0,comp) ex[i] = false; dfsone(maxel); bool can = true; repi(i,0,n) if(!ex[i] && !g2[i].empty()) { printf("-1"); can = false; break; } if(can) { while(!ansq.empty()) { int x = ansq.front(); ansq.pop(); while(!g2[x].empty()) { printf("%d ",g2[x].top()); g2[x].pop(); } } } printf("\n"); repi(i,0,n) while(!g2[i].empty()) g2[i].pop(); while(!ansq.empty()) ansq.pop(); } void refre() { kset.clear(); repi(i,0,n+1) {indeg[i] =0; e[i].clear();e2[i].clear();e3[i].clear();} } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ sc(t); while(t-- ) { sc(n);sc(m);sc(k); refre(); inp(); builddag(); #ifdef DEBUG1 repi(i,0,comp) { printf("indeg: %d, comp: %d ->> ", indeg[i], i); for(int j : e3[i]) printf("%d, ",j); printf("\n"); } #endif checkposs(); } return 0; }