#include <bits/stdc++.h> using namespace std; #define eps 0.000000001 #define for_each(i, c) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) #ifdef DEBUG #define debugendl cout << endl; #define debugp(...) printf(__VA_ARGS__) #define debuga(a, l, r) cout << #a << ":" << endl; for (int i = l; i <= r; i++) cout << a[i] << " "; cout << endl; #define debugai(a, l, r) cout << #a << ":" << endl; for (int i = l; i <= r; i++) cout << #a << "[" << i << "] = " << a[i] << endl; #define debugm(a, rl, rr, cl, cr) cout << #a << ":" << endl; for (int i = rl; i <= rr; i++) { for (int j = cl; j <= cr; j++) cout << a[i][j] << " "; cout << endl; }; cout << endl; #define debugmi(a, rl, rr, cl, cr) cout << #a << ":" << endl; for (int i = rl; i <= rr; i++) for (int j = cl; j <= cr; j++) cout << #a << "[" << i << "][" << j << "] = " << a[i][j] << endl; cout << endl; #define debugvv(a) #a << " = " << a << " " #define debugv1(a) debugvv(a) << endl #define debugv2(a, b) debugvv(a) << debugv1(b) #define debugv3(a, b, c) debugvv(a) << debugv2(b, c) #define debugv4(a, b, c, d) debugvv(a) << debugv3(b, c, d) #define debugv5(a, b, c, d, e) debugvv(a) << debugv4(b, c, d, e) #define debugv6(a, b, c, d, e, f) debugvv(a) << debugv5(b, c, d, e, f) #define debugv7(a, b, c, d, e, f, g) debugvv(a) << debugv6(b, c, d, e, f, g) #define debugv8(a, b, c, d, e, f, g, h) debugvv(a) << debugv7(b, c, d, e, f, g, h) #define get_macro(_1, _2, _3, _4, _5, _6, _7, _8, name, ...) name #define debug(...) cout << "[" << __LINE__ << "] " << get_macro(__VA_ARGS__, debugv8, debugv7, debugv6, debugv5, debugv4, debugv3, debugv2, debugv1)(__VA_ARGS__) #else #define debugendl #define debugp(...) #define debuga(a, l, r) #define debugai(a, l, r) #define debugm(a, rl, rr, cl, cr) #define debugmi(a, rl, rr, cl, cr) #define debug(...) #endif const int maxn = 100005; #define stack __stack__ vector <int> stack; int dfsNum[maxn], low[maxn]; int sccNum[maxn]; int totalSccs; bool isOnStack[maxn]; vector <int> origEdges[maxn]; int currDfsNum; void scc(int node) { dfsNum[node] = currDfsNum++; low[node] = dfsNum[node]; stack.push_back(node); isOnStack[node] = true; for_each(p, origEdges[node]) { int adjNode = *p; if (dfsNum[adjNode] == -1) { scc(adjNode); low[node] = min(low[node], low[adjNode]); } else if (isOnStack[adjNode]) { low[node] = min(low[node], low[adjNode]); } } if (low[node] == dfsNum[node]) { totalSccs++; int topOfStack; do { topOfStack = stack.back(); stack.pop_back(); isOnStack[topOfStack] = false; sccNum[topOfStack] = totalSccs; } while (topOfStack != node); } } vector <int> sccDelNodes[maxn]; vector <int> sol; void addDelNodesFromScc(int sccIdx) { debug(sccIdx); for_each(p, sccDelNodes[sccIdx]) { sol.push_back(*p); } } int goodNodes[maxn]; bool isNodeGood[maxn]; int totalGoodNodes; vector <int> sccEdges[maxn]; bool mark[maxn]; void dfs(int u) { mark[u] = true; for_each(p, sccEdges[u]) { int adjNode = *p; if (isNodeGood[adjNode] && !mark[adjNode]) { dfs(adjNode); } } } bool checkPath(int from, int to) { for (int i = 1; i <= totalGoodNodes; i++) { mark[goodNodes[i]] = false; } dfs(from); return mark[to]; } set < pair<int, int> > __set__; int delCity[maxn]; bool isDelScc[maxn]; int inDegree[maxn]; #define set __set__ void solve_test() { int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= k; i++) { scanf("%d", &delCity[i]); } for (int i = 1; i <= n; i++) { origEdges[i].clear(); } for (int i = 1; i <= m; i++) { int a, b; scanf("%d%d", &a, &b); origEdges[a].push_back(b); } sol.clear(); for (int i = 1; i <= n; i++) { sccDelNodes[i].clear(); } currDfsNum = 0; memset(dfsNum, -1, sizeof(dfsNum)); memset(isOnStack, false, sizeof(isOnStack)); stack.clear(); totalSccs = 0; for (int i = 1; i <= n; i++) { if (dfsNum[i] == -1) { scc(i); } } memset(isDelScc, false, sizeof(isDelScc)); for (int i = 1; i <= k; i++) { sccDelNodes[sccNum[delCity[i]]].push_back(delCity[i]); isDelScc[sccNum[delCity[i]]] = true; } for (int i = 1; i <= totalSccs; i++) { sort(sccDelNodes[i].begin(), sccDelNodes[i].end()); } set.clear(); for (int i = 1; i <= n; i++) { for_each(p, origEdges[i]) { if (sccNum[i] != sccNum[*p]) { set.insert(make_pair(sccNum[i], sccNum[*p])); } } } for (int i = 1; i <= n; i++) { sccEdges[i].clear(); } memset(inDegree, 0, sizeof(inDegree)); for_each(p, set) { sccEdges[p->first].push_back(p->second); inDegree[p->second]++; } stack.clear(); for (int i = 1; i <= totalSccs; i++) { if (inDegree[i] == 0) { stack.push_back(i); } } debugai(sccNum, 1, n); #ifdef DEBUG for (int i = 1; i <= totalSccs; i++) { printf("i = %d isDelScc[i] = %d\n", i, isDelScc[i]); printf("--> "); for_each(p, sccDelNodes[i]) { printf("%d ", *p); } printf("\n"); } #endif int prev = -1; totalGoodNodes = 0; while (!stack.empty()) { int curr = stack.back(); stack.pop_back(); debug(curr); if (isDelScc[curr]) { goodNodes[++totalGoodNodes] = curr; isNodeGood[ goodNodes[totalGoodNodes] ] = true; if (prev != -1) { if (!checkPath(prev, curr)) { debug(prev, curr); debugai(isNodeGood, 1, totalSccs); debugai(goodNodes, 1, totalGoodNodes); printf("-1\n"); return; } } addDelNodesFromScc(curr); prev = curr; for (int i = 1; i <= totalGoodNodes; i++) { isNodeGood[ goodNodes[i] ] = false; } totalGoodNodes = 1; goodNodes[1] = curr; isNodeGood[ goodNodes[1] ] = true; } else { goodNodes[++totalGoodNodes] = curr; isNodeGood[ goodNodes[totalGoodNodes] ] = true; } for_each(p, sccEdges[curr]) { inDegree[*p]--; if (inDegree[*p] == 0) { stack.push_back(*p); } } } for (int i = 0, sz = sol.size(); i < sz; i++) { printf("%d ", sol[i]); } printf("\n"); } void solve() { int t; scanf("%d", &t); while (t--) { solve_test(); } } int main() { clock_t starttime = clock(); solve(); clock_t endtime = clock(); debugp("time taken: %.2lfs\n", (double)(endtime - starttime) / CLOCKS_PER_SEC); return 0; }