#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <set> #include <queue> const int N = 100010; using namespace std; int level[N], DFN[N], LOW[N], Stap[N], Belong[N]; int indgr[N], outdgr[N]; int Stop, Bcnt, Dindex; int t, n, m, x, y, k; bool instack[N], tag[N], finded = false; vector <int> v[N], comp[N], levels[N], topo_order, res; set <int> se[N], cities; void tarjan(int i) { int j; DFN[i] = LOW[i] = ++Dindex; instack[i] = true; Stap[++Stop] = i; for (int k = 0;k < v[i].size(); ++k) { j = v[i][k]; if (!DFN[j]) { tarjan(j); if (LOW[j] < LOW[i]) LOW[i] = LOW[j]; } else if (instack[j] && DFN[j] < LOW[i]) LOW[i] = DFN[j]; } if (DFN[i] == LOW[i]) { ++Bcnt; do { j = Stap[Stop--]; instack[j] = false; Belong[j] = Bcnt; } while (j != i); } } void dfs(int u, int goal) { //printf("U: %d %d\n", u, goal); if (u == goal) finded = true; if (finded || level[u] >= level[goal]) return; for (set<int>::iterator iter = se[u].begin();iter != se[u].end(); ++iter) { //printf("iter: %d %d\n", *iter, tag[*iter]); if (!tag[*iter]) { if (level[*iter] <= level[goal]) { tag[*iter] = true; dfs(*iter, goal); } } } } bool is_valid(void) { memset(tag, 0, sizeof(tag)); //printf("k: %d\n", k); for (int i = 1;i < k;++i) { int a = Belong[res[i - 1]]; int b = Belong[res[i]]; finded = false; dfs(a, b); //printf("prev and cur: %d %d\n", res[i - 1], res[i]); //printf("a b finded: %d %d %d\n", a, b, finded); //printf("level: %d %d\n", level[a], level[b]); //edge: a -> b if (!finded) return false; } return true; } void cal() { Bcnt = 0; memset(DFN, 0, sizeof(DFN)); memset(instack, false, sizeof(instack)); memset(indgr, 0, sizeof(indgr)); memset(level, 0, sizeof(level)); for (int i = 1;i <= n; ++i) if (!DFN[i]) tarjan(i); for (int i = 1;i <= n;++i) { comp[ Belong[i] ].push_back(i); int k = v[i].size(); for (int j = 0;j < k;++j) { if (Belong[i] != Belong[v[i][j]] && se[Belong[i]].find(Belong[v[i][j]]) == se[Belong[i]].end()) { indgr[ Belong[v[i][j]] ]++; se[ Belong[i] ].insert( Belong[v[i][j]] ); } } } for (int i = 1;i <= Bcnt;++i) sort(comp[i].begin(), comp[i].end()); queue<int> q; //for (int i = 1;i <= Bcnt;++i) //{ // printf("comp #%d\n", i); // for (int j = 0;j < comp[i].size();++j) // printf("%d ", comp[i][j]); // printf("\n"); //} for (int i = 1;i <= Bcnt;++i) { //printf("in deg: %d\n", indgr[i]); if (indgr[i] == 0) { q.push(i); level[i] = 0; } } while (!q.empty()) { int fr = q.front(); //printf("fr: %d\n", fr); topo_order.push_back(fr); q.pop(); for (set<int>::iterator iter = se[fr].begin();iter != se[fr].end();++iter) { //printf("star iter: %d %d\n", *iter, indgr[*iter]); int adj_comp = *iter; indgr[adj_comp]--; if (indgr[adj_comp] == 0) { q.push(adj_comp); level[adj_comp] = level[fr] + 1; } } } //printf("topo order size: %d\n", topo_order.size()); int city_count = 0; for (int i = 0;i < Bcnt;++i) { int cur = topo_order[i]; int k = comp[cur].size(); for (int j = 0;j < k;++j) { if (cities.find(comp[cur][j]) != cities.end()) { res.push_back(comp[cur][j]); ++city_count; } } } //printf("city count: %d\n", city_count); if (city_count != k || !is_valid()) printf("-1\n"); else { for (int i = 0;i < k;++i) { printf("%d", res[i]); if (i == k - 1) printf("\n"); else printf(" "); } } } int main() { int c; scanf("%d", &t); while(t--) { scanf("%d", &n); for(int i = 1;i <= n;++i) { v[i].clear(); comp[i].clear(); se[i].clear(); levels[i].clear(); } cities.clear(); topo_order.clear(); res.clear(); scanf("%d%d", &m, &k); for (int i = 1;i <= k;++i) { scanf("%d", &c); cities.insert(c); } for(int i = 1;i <= m;++i) { scanf("%d%d", &x, &y); v[x].push_back(y); } cal(); } return 0; }