#include<stdio.h> #include<algorithm> #include<stack> #include<vector> #include<set> #include<limits.h> using namespace std; const int max_v = 200000 + 5; int v; vector<int> adj_list[max_v]; bool visited[max_v]; int scc[max_v]; vector<int> rev_adj_list[max_v]; int dag_v; vector<int> dag_adj_list[max_v]; int vis[max_v]; void dfs_rev(int i, stack<int>& s) { if(visited[i]) return; visited[i] = true; for(int j=0; j<rev_adj_list[i].size(); ++j) dfs_rev(rev_adj_list[i][j], s); s.push(i); } stack<int> reverse_dfs_order() { stack<int> s; for(int i=0; i<v; ++i) visited[i] = false; for(int i=0; i<v; ++i) if(!visited[i]) dfs_rev(i, s); return s; } void dfs_fill(int i, int component) { if(visited[i]) return; visited[i] = true; scc[i] = component; for(int j=0; j<adj_list[i].size(); ++j) dfs_fill(adj_list[i][j], component); } int kosaraju_scc() { // Compute reverse graph for(int i=0; i<v; ++i) for(int j=0; j<adj_list[i].size(); ++j) rev_adj_list[adj_list[i][j]].push_back(i); stack<int> s = reverse_dfs_order(); // DFS graph in the computed order int component = 0; for(int i=0; i<v; ++i) visited[i] = false; while(!s.empty()) { int curr = s.top(); s.pop(); if(!visited[curr]) { dfs_fill(curr, component); component++; } } // Clear reverse adjacency list for(int i=0; i<v; ++i) rev_adj_list[i].clear(); return component; } int in_degree[max_v]; // Returns a vector of vertices if there is no negative cycle // Else returns an empty vector // Set s can be replaced by any collection like stack, queue, priority queue, etc vector<int> topological_sort() { for(int i=0; i<dag_v; ++i) in_degree[i] = 0; for(int i=0; i<dag_v; ++i) for(int j=0; j<dag_adj_list[i].size(); ++j) in_degree[dag_adj_list[i][j]]++; set<int> s; vector<int> l; for(int i=0; i<dag_v; ++i) if(in_degree[i] == 0) s.insert(i); while(!s.empty()) { set<int>::iterator it = s.begin(); int u = *it; s.erase(it); l.push_back(u); for(int i=0; i<dag_adj_list[u].size(); ++i) { int w = dag_adj_list[u][i]; in_degree[w]--; if(in_degree[w] == 0) s.insert(w); } } for(int i=0; i<dag_v; ++i) if(in_degree[i] > 0) return vector<int>(); return l; } void help_dfs_dag(int i) { if(visited[i]) return; visited[i] = true; for(int j=0; j<dag_adj_list[i].size(); ++j) help_dfs_dag(dag_adj_list[i][j]); } void dfs_dag(int start) { for(int i=0; i<dag_v; ++i) visited[i] = false; help_dfs_dag(start); } void help_dfs_orig(int i) { if(visited[i]) return; visited[i] = true; for(int j=0; j<dag_adj_list[i].size(); ++j) help_dfs_dag(dag_adj_list[i][j]); } void dfs_orig(int start) { for(int i=0; i<dag_v; ++i) visited[i] = false; help_dfs_dag(start); } int dist[20][20]; int adj_mat[20][20]; void floyd_warshall() { for(int i=0; i<v; ++i) { for(int j=0; j<v; ++j) { dist[i][j] = (adj_mat[i][j] == 0) ? 1000000 : adj_mat[i][j]; } if(dist[i][i] > 0) dist[i][i] = 0; } for(int k=0; k<v; ++k) { for(int i=0; i<v; ++i) { for(int j=0; j<v; ++j) { if(dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } /*for(int i=0; i<v; ++i) { for(int j=0; j<v; ++j) { printf("%d %d = %d\n", i, j, dist[i][j]); } }*/ } int main() { int T; scanf("%d", &T); int t = 0; int tt = T; while(T--) { int N,M,K; scanf("%d %d %d", &N, &M, &K); v = N; set<int> cities; for(int i=0; i<K; ++i) { int city; scanf("%d", &city); cities.insert(city-1); } for(int m=0; m<M; ++m) { int x,y; scanf("%d %d", &x, &y); adj_list[x-1].push_back(y-1); } if(N <= 10) { vector<int> cits; for(set<int>::iterator it = cities.begin(); it != cities.end(); ++it) cits.push_back(*it); for(int i=0; i<20; ++i) for(int j=0; j<20; ++j) adj_mat[i][j] = 0; for(int i=0; i<v; ++i) for(int j=0; j<adj_list[i].size(); ++j) adj_mat[i][adj_list[i][j]] = 1; floyd_warshall(); sort(cits.begin(), cits.end()); bool flag = false; do { bool cur_flag = true; for(int i=1; i<K; ++i) { if(dist[cits[i-1]][cits[i]] >= 1000000) { cur_flag = false; break; } } if(cur_flag) { for(int i=0; i<K-1; ++i) printf("%d ", cits[i]+1); printf("%d\n", cits[K-1]+1); flag = true; break; } } while(next_permutation(cits.begin(), cits.end())); if(!flag) printf("-1\n"); // Clear adj lists for(int i=0; i<v; ++i) adj_list[i].clear(); continue; } // Divide into SCC's // Get component of each SCC dag_v = kosaraju_scc(); set<int> setset[max_v]; for(int i=0; i<v; ++i) { if(cities.find(i) != cities.end()) { setset[scc[i]].insert(i); } for(int j=0; j<adj_list[i].size(); ++j) { int w = adj_list[i][j]; if(scc[i] != scc[w]) dag_adj_list[scc[i]].push_back(scc[w]); } } vector<int> top_order = topological_sort(); int start; for(vector<int>::iterator it = top_order.begin(); it != top_order.end(); ++it) { int curr_scc = *it; if(setset[curr_scc].size()) { start = curr_scc; break; } } dfs_dag(start); bool flag = true; for(int i=0; i<dag_v; ++i) { if(setset[i].size()) { if(!visited[i]) { flag = false; break; } } } if(!flag) printf("-1"); else { for(vector<int>::iterator it1 = top_order.begin(); it1 != top_order.end(); ++it1) { int curr_scc = *it1; if(setset[curr_scc].size()) { for(set<int>::iterator it = setset[curr_scc].begin(); it != setset[curr_scc].end(); ++it) { printf("%d ", (*it) + 1); } } } } printf("\n"); // Clear adj lists for(int i=0; i<v; ++i) adj_list[i].clear(); for(int i=0; i<dag_v; ++i) dag_adj_list[i].clear(); } return 0; }