#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <vector> #include <stack> using namespace std; #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++) #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--) #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--) #define DRI(a) int a; scanf("%d ", &a); #define DRII(a, b) int a, b; scanf("%d %d ", &a, &b); #define DRIII(a, b, c) int a, b, c; scanf("%d %d %d ", &a, &b, &c); #define DRIIII(a, b, c, d) int a, b, c, d; scanf("%d %d %d %d ", &a, &b, &c, &d); #define RI(a) scanf("%d ", &a); #define RII(a, b) scanf("%d %d ", &a, &b); #define RIII(a, b, c) scanf("%d %d %d ", &a, &b, &c); #define RIIII(a, b, c, d) scanf("%d %d %d %d ", &a, &b, &c, &d); #define PB push_back #define MP make_pair #define ff first #define ss second #define vi vector<int> #define pii pair<int,int> #define ll long long #define ull unsigned long long #define MM(co, cim) memset((co), (cim), sizeof((co))) #define DEB(x) cerr << ">>> " << #x << " : " << x << endl; vi toVisit; vi g[100007]; vi gr[100007]; bool vis[100007]; bool isInteresting[100007]; bool isInterestingGroup[100007]; stack<int> st; int inGroup[100007]; vi group[100007]; int groups; vi interestingInGroup[100007]; vi gg[100007]; vi ggr[100007]; int ggIn[100007]; int ggOut[100007]; int ggOrder[100007]; vi interrestingSorted; int nextInterresting[100007]; void DFS1(int v) { if(vis[v]) return; vis[v] = true; FOR(i,0,g[v].size()) { int u = g[v][i]; DFS1(u); } st.push(v); } void DFS2(int v) { if(vis[v]) return; //DEB(v); vis[v] = true; FOR(i,0,gr[v].size()) { int u = gr[v][i]; DFS2(u); } group[groups].PB(v); inGroup[v] = groups; } int main () { DRI(T); while(T--) { DRIII(N,M,K); toVisit.clear(); MM(vis,false); MM(isInteresting,false); MM(isInterestingGroup,false); MM(inGroup,0); groups = 0; MM(ggIn,0); MM(ggOut,0); MM(ggOrder,0); MM(nextInterresting,-1); interrestingSorted.clear(); FOR(i,0,100007) { g[i].clear(); gr[i].clear(); group[i].clear(); interestingInGroup[i].clear(); gg[i].clear(); ggr[i].clear(); } FOR(i,0,K) { DRI(a); toVisit.PB(a); isInteresting[a] = true; } FOR(i,0,M) { DRII(a,b); g[a].PB(b); gr[b].PB(a); } MM(vis,false); FOR(i,1,N+1) DFS1(i); MM(vis,false); groups = 0; while(!st.empty()) { int v = st.top(); st.pop(); if(vis[v]) continue; DFS2(v); groups++; } //DEB(groups); FOR(i,1,N+1) { int v = i; FOR(j,0,g[v].size()) { int u = g[v][j]; if(inGroup[v] != inGroup[u]) { gg[inGroup[v]].PB(inGroup[u]); } } } FOR(i,0,groups) { sort(gg[i].begin(), gg[i].end()); vi::iterator it = unique(gg[i].begin(), gg[i].end()); gg[i].resize(distance(gg[i].begin(),it)); FOR(j,0,gg[i].size()) ggIn[gg[i][j]]++; } FOR(i,0,groups) { int v = i; FOR(j,0,gg[v].size()) { int u = gg[v][j]; ggr[u].PB(v); } ggOut[v] = gg[v].size(); } /* // print FOR(i,0,groups) { cout << "group " << i << ": in " << ggIn[i] << " out: "; FOR(j,0,gg[i].size()) { cout << gg[i][j] << " "; } cout << endl; } */ int interestingGroupsLeft = 0; FOR(i,0,groups) { FOR(j,0,group[i].size()) { if(isInteresting[group[i][j]]) { isInterestingGroup[i] = true; interestingInGroup[i].PB(group[i][j]); } } if(isInterestingGroup[i]) { sort(interestingInGroup[i].begin(),interestingInGroup[i].end()); interestingGroupsLeft++; } } MM(vis,false); int orderCnt = 0; queue<int> q; FOR(i,0,groups) if(ggIn[i] == 0) q.push(i); while(!q.empty()) { int v = q.front(); q.pop(); if(vis[v]) continue; vis[v] = true; if(isInterestingGroup[v]) { interrestingSorted.PB(v); } ggOrder[v] = orderCnt++; FOR(i,0,gg[v].size()) { int u = gg[v][i]; if(--ggIn[u] == 0) q.push(u); } } MM(vis,false); FOR(i,0,groups) if(ggOut[i] == 0) q.push(i); while(!q.empty()) { int v = q.front(); q.pop(); if(vis[v]) continue; vis[v] = true; int nxt = nextInterresting[v]; if(isInterestingGroup[v]) { if(nxt == -1) nxt = v; else if(ggOrder[v] < ggOrder[nxt]) nxt = v; } FOR(i,0,ggr[v].size()) { int u = ggr[v][i]; if(--ggOut[u] == 0) q.push(u); if(nextInterresting[u] == -1) nextInterresting[u] = nxt; else if(nxt != -1 && ggOrder[nxt] < ggOrder[nextInterresting[u]]) nextInterresting[u] = nxt; } } bool ok = true; FOR(i,0,interrestingSorted.size()-1) { int v = interrestingSorted[i]; int nxt = interrestingSorted[i+1]; if(nextInterresting[v] != nxt) ok = false; } if(ok) { FOR(i,0,interrestingSorted.size()) { int v = interrestingSorted[i]; FOR(j,0,interestingInGroup[v].size()) { cout << interestingInGroup[v][j] << " "; } } cout << endl; } else { cout << -1 << endl; } /* // print FOR(i,0,groups) { cout << "group " << i << " int? " << isInterestingGroup[i] << " order: " << ggOrder[i] << endl; } */ } return 0; }