#include <bits/stdc++.h> using namespace std; #define dbg(...) dbs(#__VA_ARGS__, __VA_ARGS__) template <class T> void dbs(string str, T t) { cerr << str << " : " << t << "\n"; } template <class T, class... S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...); } const int MAX_N = 100010; stack <int> dfs_scc; bool in_stack[MAX_N]; int dfs_low[MAX_N]; int dfs_num[MAX_N]; int counter; bool scc_vis[MAX_N]; vector<int> adl[MAX_N]; int compCounter; int compId[MAX_N]; vector <int> comp[MAX_N]; void tarjanSCC(int u) { dfs_low[u] = dfs_num[u] = counter++; scc_vis[u] = true; dfs_scc.push(u); in_stack[u] = true; for(int i = 0;i < adl[u].size();i++) { int v = adl[u][i]; if(!scc_vis[v]) tarjanSCC(v); if(in_stack[v]) dfs_low[u] = min(dfs_low[u], dfs_low[v]); } if(dfs_low[u] == dfs_num[u]) { while(dfs_scc.size() && dfs_scc.top() != u) { in_stack[dfs_scc.top()] = 0; comp[compCounter].push_back(dfs_scc.top()); compId[dfs_scc.top()] = compCounter; dfs_scc.pop(); } in_stack[u]=0; comp[compCounter].push_back(dfs_scc.top()); compId[dfs_scc.top()] = compCounter; dfs_scc.pop(); ++compCounter; } } vector <int> adjSCC[MAX_N], inSCC[MAX_N]; bool needSCC[MAX_N]; bool visSCC[MAX_N]; int parent[MAX_N]; int inDeg[MAX_N]; vector <int> topSort; void dfs(int u) { if (visSCC[u]) return; visSCC[u] = true; for (int v : adjSCC[u]) if (!visSCC[v]) { dfs(v); } topSort.push_back(u); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int tc; cin >> tc; while (tc--) { int n, m, k; cin >> n >> m >> k; vector <int> cities(k); set <int> good; for (int i = 0; i < k; ++i) { cin >> cities[i]; --cities[i]; good.insert(cities[i]); } for (int i = 0; i < n; ++i) { adl[i].clear(); comp[i].clear(); } vector < pair <int, int> > edges(m); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u, --v; edges[i] = make_pair(u, v); adl[u].push_back(v); } while (!dfs_scc.empty()) dfs_scc.pop(); fill(in_stack, in_stack + n, false); fill(scc_vis, scc_vis + n, false); compCounter = 0, counter = 0; for (int i = 0; i < n; ++i) if (!scc_vis[i]) { tarjanSCC(i); } // for (int i = 0; i < n; ++i) { // dbg(i, compId[i]); // } bool allSame = true; for (int i = 0; i < k; ++i) { if (compId[cities[i]] != compId[cities[0]]) { allSame = false; break; } } if (allSame) { sort(cities.begin(), cities.end()); for (int i = 0; i < k; ++i) { cout << cities[i] + 1 << " "; } cout << "\n"; continue; } for (int i = 0; i < compCounter; ++i) { adjSCC[i].clear(); inSCC[i].clear(); } for (int i = 0; i < m; ++i) { int u = edges[i].first; int v = edges[i].second; if (compId[u] != compId[v]) { adjSCC[compId[u]].push_back(compId[v]); } } for (int i = 0; i < compCounter; ++i) if (!adjSCC[i].empty()) { sort(adjSCC[i].begin(), adjSCC[i].end()); adjSCC[i].erase(unique(adjSCC[i].begin(), adjSCC[i].end()), adjSCC[i].end()); // dbg(i); // for (int j : adjSCC[i]) // cerr << j << " "; // cerr << "\n"; } fill(inDeg, inDeg + compCounter, 0); for (int i = 0; i < compCounter; ++i) { for (int j : adjSCC[i]) { ++inDeg[j]; inSCC[j].push_back(i); } } fill(needSCC, needSCC + compCounter, false); for (int i = 0; i < k; ++i) { needSCC[compId[cities[i]]] = true; } int need = 0; for (int i = 0; i < compCounter; ++i) need += needSCC[i]; // for (int i = 0; i < compCounter; ++i) { // dbg(i, inDeg[i]); // } fill(parent, parent + compCounter, -1); vector <int> dp(compCounter, 0); int p = -1; topSort.clear(); fill(visSCC, visSCC + compCounter, false); for (int i = 0; i < compCounter; ++i) if (!visSCC[i]) { dfs(i); } reverse(topSort.begin(), topSort.end()); for (int u : topSort) { parent[u] = -1; dp[u] = needSCC[u]; for (int v : inSCC[u]) { if (dp[u] < dp[v] + needSCC[u]) { dp[u] = dp[v] + needSCC[u]; parent[u] = v; } } if (dp[u] == need) { p = u; break; } } if (p == -1) { cout << "-1\n"; } else { vector <int> path; while (p != -1) { path.push_back(p); p = parent[p]; } reverse(path.begin(), path.end()); vector <int> ans; for (int i = 0; i < path.size(); ++i) { int id = path[i]; sort(comp[id].begin(), comp[id].end()); for (int u : comp[id]) { if (good.count(u)) { ans.push_back(u + 1); } } } assert(ans.size() == k); for (int i = 0; i < ans.size(); ++i) { cout << ans[i] << " "; } cout << "\n"; } } return 0; }