#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <set> #include <queue> using namespace std; const int NMAX = 100010; int T, K, N, V[NMAX], M, X[2 * NMAX], Y[2 * NMAX], Which[NMAX], TopSort[NMAX], TSPos[NMAX]; vector<int> G[NMAX], GT[NMAX], NodesCTC[NMAX]; set<int> CTCG[NMAX]; bool Used[NMAX], Special[NMAX]; void DFP(int Node) { Used[Node] = 1; for(int Vec : G[Node]) if(!Used[Vec]) DFP(Vec); TopSort[++ TopSort[0]] = Node; } void DFM(int Node, int IndexCTC) { Used[Node] = 0; Which[Node] = IndexCTC; for(int Vec : GT[Node]) if(Used[Vec]) DFM(Vec, IndexCTC); } void DFSCTC(int Node) { Used[Node] = 1; for(int Vec : CTCG[Node]) if(!Used[Vec]) DFSCTC(Vec); TopSort[++ TopSort[0]] = Node; } void BFS(int Start, int Limit) { queue<int> Q; Q.push(Start); Used[Start] = 1; while(!Q.empty()) { int Node = Q.front(); Q.pop(); for(int Vec : CTCG[ TopSort[Node] ]) if(!Used[ TSPos[Vec] ] && TSPos[Vec] <= Limit) { Used[TSPos[Vec]] = 1; Q.push(TSPos[Vec]); } } } int main() { // freopen("in", "r", stdin); // freopen("out", "w", stdout); scanf("%i", &T); for(; T; T --) { scanf("%i %i %i", &N, &M, &K); TopSort[0] = 0; for(int i = 1; i <= N; ++ i) { TopSort[i] = 0; Which[i] = 0; G[i].clear(); GT[i].clear(); CTCG[i].clear(); NodesCTC[i].clear(); Used[i] = 0; Special[i] = 0; TSPos[i] = 0; } for(int i = 1; i <= K; ++ i) scanf("%i", &V[i]); for(int i = 1; i <= M; ++ i) { scanf("%i %i", &X[i], &Y[i]); G[X[i]].push_back(Y[i]); GT[Y[i]].push_back(X[i]); } for(int i = 1; i <= N; ++ i) if(!Used[i]) DFP(i); int NrCTC = 0; for(int i = TopSort[0]; i; -- i) if(Used[TopSort[i]]) ++ NrCTC, DFM(TopSort[i], NrCTC); // for(int i = 1; i <= N; ++ i) printf("Nodul %i in CTC %i\n", i, Which[i]); for(int i = 1; i <= M; ++ i) if(Which[X[i]] != Which[Y[i]])/* printf("Muchie de la %i la %i\n", Which[X[i]], Which[Y[i]]), */CTCG[ Which[X[i]] ].insert(Which[Y[i]]); for(int i = 1; i <= K; ++ i) NodesCTC[ Which[V[i]] ].push_back(V[i]), Special[ Which[V[i]] ] = 1; for(int i = 1; i <= NrCTC; ++ i) sort(NodesCTC[i].begin(), NodesCTC[i].end()); TopSort[0] = 0; for(int i = 1; i <= NrCTC; ++ i) if(!Used[i]) DFSCTC(i); reverse(TopSort + 1, TopSort + TopSort[0] + 1); /* for(int i = 1; i <= NrCTC; ++ i) printf("%i ", TopSort[i]); printf("\n");*/ for(int i = 1; i <= NrCTC; ++ i) TSPos[TopSort[i]] = i; vector<int> Order; for(int i = 1; i <= NrCTC; ++ i) Used[i] = 0; for(int i = 1; i <= NrCTC; ++ i) if(Special[TopSort[i]]) Order.push_back(i); /* for(int i = 0; i < Order.size(); ++ i) printf("%i ", Order[i]); printf("\n");*/ bool Bad = 0; for(int i = 0; i < int(Order.size()) - 1; ++ i) { BFS(Order[i], Order[i + 1]); if(!Used[ Order[i + 1] ]) { Bad = 1; break; } } if(Bad) printf("-1\n"); else { for(int i = 0; i < Order.size(); ++ i) for(int j = 0; j < NodesCTC[ TopSort[Order[i]] ].size(); ++ j) printf("%i ", NodesCTC[ TopSort[Order[i]] ][j]); printf("\n"); } } }