#include<iostream> #include<vector> #include<algorithm> #define f first #define s second #define mp make_pair using namespace std; template<int N> struct graph { vector<int> conn[N]; vector<int> revconn[N]; void addEdge(int a, int b) { conn[a].push_back(b); revconn[b].push_back(a); } //Here we implement the topological sorting vector<int> topsorted; bool explr[N]; void topsortdfs(int pos) { if(explr[pos]) return; explr[pos] = true; for(int i=0;i<revconn[pos].size();i++) topsortdfs(revconn[pos][i]); topsorted.push_back(pos); } void topsort() { fill(explr, explr + N, false); for(int i=0;i<N;i++) topsortdfs(i); reverse(topsorted.begin(), topsorted.end() ); } //Here we implement the scc finding vector<int> scc[N]; int numsccs; int inScc[N]; void sccDFS(int pos) { if(explr[pos]) return; explr[pos] = true; inScc[pos] = numsccs; scc[numsccs].push_back(pos); for(int i=0;i<conn[pos].size();i++) sccDFS(conn[pos][i]); } void getSCC() { topsort(); numsccs = 0; fill(explr, explr + N, false); for(int i=0;i<N;i++) { sccDFS(topsorted[i]); if(scc[numsccs].size() > 0) numsccs++; } } //Build a tree on top of the scc vector<int> sccConn[N]; int sccParent[N], level[N]; void buildSccTree() { getSCC(); fill(sccParent, sccParent + N, -1); for(int i=0;i<N;i++) for(int j=0;j<conn[i].size();j++) { int l = inScc[i], r = inScc[conn[i][j]]; sccConn[l].push_back(r); } } //Finally solve the problem vector<int> backtrace; bool solvedfs(int start, int fin) { if(explr[start]) return false; explr[start] = true; backtrace.push_back(start); if(start == fin) return true; if(start < fin) return false; for(unsigned int i=0;i<sccConn[start].size();i++) if(solvedfs(sccConn[start][i], fin) ) return true; return false; } bool solve(vector<int> &nodes, vector<int> &out) { buildSccTree(); fill(explr, explr + N, false); //format(depth, index) vector<pair<int, int> > depthsorted; for(int i=0;i<nodes.size();i++) depthsorted.push_back( mp(-inScc[nodes[i]], nodes[i] ) ); sort(depthsorted.begin(), depthsorted.end() ); for(int i=0;i+1<depthsorted.size();i++) { if(!solvedfs(-depthsorted[i].f, -depthsorted[i+1].f) ) return false; for(unsigned int i=0;i<backtrace.size();i++) explr[backtrace[i]] = false; backtrace.clear(); } for(int i=0;i<depthsorted.size();i++) out.push_back(depthsorted[i].s); return true; } }; //------------------------------------------------------------------------------------ //Main function here int t, n, m, k, p1, p2; int main() { cin.sync_with_stdio(false); cin >> t; for(int TCASE = 0; TCASE < t; TCASE++) { cin >> n >> m >> k; vector<int> needToVisit; for(int i=0;i<k;i++) { cin >> p1; needToVisit.push_back(p1-1); } graph<100000> *g = new graph<100000>; for(int i=0;i<m;i++) { cin >> p1 >> p2; g->addEdge(p1-1, p2-1); } vector<int> res; bool solved = g->solve(needToVisit, res); if(!solved) cout << "-1\n"; else { cout << res[0] + 1; for(unsigned int i=1;i<res.size();i++) cout << ' ' << res[i] + 1; cout << '\n'; } } return 0; }