/* DIKRA */ /* DELAPAN.3gp */ #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <utility> #include <numeric> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <ctime> #include <cassert> using namespace std; #ifdef DEBUG #define debug(...) printf(__VA_ARGS__) #define GetTime() fprintf(stderr,"Running time: %.3lf second\n",((double)clock())/CLOCKS_PER_SEC) #else #define debug(...) #define GetTime() #endif //type definitions typedef long long ll; typedef double db; typedef pair<int,int> pii; typedef vector<int> vint; //abbreviations #define A first #define B second #define MP make_pair #define PB push_back //macros #define REP(i,n) for (int i = 0; i < (n); ++i) #define REPD(i,n) for (int i = (n)-1; 0 <= i; --i) #define FOR(i,a,b) for (int i = (a); i <= (b); ++i) #define FORD(i,a,b) for (int i = (a); (b) <= i; --i) #define FORIT(it,c) for (__typeof ((c).begin()) it = (c).begin(); it != (c).end(); it++) #define ALL(a) (a).begin(),(a).end() #define SZ(a) ((int)(a).size()) #define RESET(a,x) memset(a,x,sizeof(a)) #define EXIST(a,s) ((s).find(a) != (s).end()) #define MX(a,b) a = max((a),(b)); #define MN(a,b) a = min((a),(b)); inline void OPEN(const string &s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } /* -------------- end of DELAPAN.3gp's template -------------- */ #define INF 1000000000 #define MAXN 100005 int ntc; int n, m, nk; vector<int> adj[MAXN]; int vis[MAXN]; vector<int> sccStack; int sccTime; int lowlink[MAXN]; vector<vector<int> > components; vector<int> order; int tocmp[MAXN]; int compscore[MAXN]; vector<int> nuadj[MAXN]; vector<vector<int> > compmust; int mustvisit[MAXN]; int indeg[MAXN]; queue<int> topoq; vector<int> ans; int cumscore[MAXN]; void loadGraph(){ scanf("%d %d %d", &n, &m, &nk); for (int i = 1; i <= n; ++i) adj[i].clear(); RESET(mustvisit, 0); REP(i, nk){ int x; scanf("%d", &x); mustvisit[x] = 1; // printf("mustvisit %d!\n", x); } for (int i = 0; i < m; ++i){ int x, y; scanf("%d %d", &x, &y); adj[x].push_back(y); } } void dfsScc(int u){ lowlink[u] = sccTime++; vis[u] = 1; sccStack.push_back(u); int isComponentRoot = 1; for (int i = 0; i < adj[u].size(); ++i){ int v = adj[u][i]; if (!vis[v]){ dfsScc(v); } if (lowlink[u] > lowlink[v]){ lowlink[u] = lowlink[v]; isComponentRoot = 0; } } if (isComponentRoot){ vector<int> component; component.clear(); while (1){ int x = sccStack.back(); sccStack.pop_back(); component.push_back(x); lowlink[x] = INF; if (x == u) break; } components.push_back(component); } } void findScc(){ memset(vis, 0, sizeof(vis)); sccStack.clear(); components.clear(); memset(lowlink, 0, sizeof(lowlink)); sccTime = 0; for (int v = 1; v <= n; ++v){ if (!vis[v]){ dfsScc(v); } } } void initScc(){ RESET(compscore, 0); compmust.clear(); for (int i = 0; i < components.size(); ++i){ vector<int> &vc = components[i]; vector<int> mustlist; mustlist.clear(); compscore[i] = 0; REP(j, SZ(vc)){ tocmp[vc[j]] = i; compscore[i] += mustvisit[vc[j]]; // printf("vc -> %d, mustvisit = %d\n", vc[j], mustvisit[vc[j]]); if (mustvisit[vc[j]]) mustlist.PB(vc[j]); } sort(mustlist.begin(), mustlist.end()); compmust.PB(mustlist); // printf("component[%d] -> compmust = %d\n", i, SZ(compmust[i])); } REP(i, SZ(components)){ vector<int> &vc = components[i]; nuadj[i].clear(); REP(j, SZ(vc)){ int u = vc[j]; REP(k, SZ(adj[u])){ if (tocmp[adj[u][k]] != i) nuadj[i].PB(tocmp[adj[u][k]]); } } sort(nuadj[i].begin(), nuadj[i].end()); nuadj[i].erase(unique(nuadj[i].begin(), nuadj[i].end()), nuadj[i].end()); } } void toposortScc(){ RESET(indeg, 0); REP(i, SZ(components)){ // printf("nuadj[%d] = ", i); REP(j, SZ(nuadj[i])){ ++indeg[nuadj[i][j]]; // printf(" %d", nuadj[i][j]); } // printf("\n"); } while (SZ(topoq)) topoq.pop(); REP(i, SZ(components)){ // printf("indeg[%d] = %d\n", i, indeg[i]); if (indeg[i] == 0) topoq.push(i); } order.clear(); while (SZ(topoq)){ int now = topoq.front(); topoq.pop(); order.PB(now); REP(i, SZ(nuadj[now])){ int u = nuadj[now][i]; --indeg[u]; if (indeg[u] == 0){ topoq.push(u); } } } // printf("order: "); // REP(i, SZ(order)) printf(" %d", order[i]); // printf("\n"); } void printScc(){ for (int i = 0; i < components.size(); ++i){ vector<int> &vc = components[i]; printf("scc-%d:", i); REP(j, SZ(vc)){ printf(" %d", vc[j]); } printf("\n"); printf("score[%d] = %d, cumscore = %d\n", i, compscore[i], cumscore[i]); } } void initScore(){ RESET(cumscore, 0); for (int i = SZ(order)-1; i >= 0; --i){ int u = order[i]; cumscore[u] = compscore[u]; int add = 0; REP(j, SZ(nuadj[u])){ MX(add,cumscore[nuadj[u][j]]); } cumscore[u] += add; } } void dfsans(int now){ while (SZ(ans) < nk){ int ne = -1; REP(i, SZ(compmust[now])){ ans.PB(compmust[now][i]); } // printf("now = %d, ans: ", now); // REP(i, SZ(ans)) printf(" %d", ans[i]); // printf("\n"); REP(i, SZ(nuadj[now])){ int u = nuadj[now][i]; if (SZ(ans) + cumscore[u] == nk){ ne = u; break; } } if (ne == -1) break; now = ne; } } int main(){ int ntc; scanf("%d", &ntc); while (ntc--){ // printf("\n\n"); loadGraph(); findScc(); initScc(); toposortScc(); initScore(); // printScc(); RESET(vis, 0); ans.clear(); REP(i, SZ(order)){ if (cumscore[order[i]] == nk){ dfsans(order[i]); break; } } if (SZ(ans) == nk){ REP(i, SZ(ans)){ if (i) printf(" "); printf("%d", ans[i]); } printf("\n"); } else { printf("-1\n"); } } return 0; }