#include <algorithm> #include <cassert> #include <cstdio> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> constexpr int N = 100010; std::vector<int> adj[N]; std::vector<int> adj_rev[N]; bool is_in_path[N]; int path[N]; int scc_cnt; int scc_id[N]; bool vis[N]; std::stack<int> verts; std::vector<int> scc[N]; std::vector<int> scc_adj[N]; int parent[N]; int scc_topo_pos[N]; std::stack<int> scc_topo_verts; int tin[N], tout[N], dt; void dfs(int u) { if (vis[u]) return; vis[u] = true; for (int v : adj[u]) { dfs(v); } verts.push(u); } void dfs_rev(int u) { if (vis[u]) return; vis[u] = true; scc_id[u] = scc_cnt; scc[scc_cnt].push_back(u); for (int v : adj_rev[u]) { dfs_rev(v); } } void dfs_scc_topo(int u) { if (vis[u]) return; vis[u] = true; tin[u] = ++dt; for (int v : scc_adj[u]) { dfs_scc_topo(v); } tout[u] = ++dt; scc_topo_verts.push(u); scc_topo_pos[u] = (int) scc_topo_verts.size(); } bool is_reachable(int u, int v) { for (int k : scc_adj[u]) { if (k == v) return true; // if (is_in_path[k]) continue; if (is_reachable(k, v)) return true; } return false; } int main(int argc, const char* argv[]) { // freopen("/Volumes/SSD-Xcode/Android/projects/mep/mepcpp/mepcpp/in", "r", stdin); std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int tn; std::cin >> tn; while (tn--) { int n, m, k; std::cin >> n >> m >> k; for (int i = 1; i <= n; ++i) { adj[i].clear(); adj_rev[i].clear(); } for (int i = 1; i <= k; ++i) { std::cin >> path[i]; } for (int i = 1; i <= m; ++i) { int u, v; std::cin >> u >> v; adj[u].push_back(v); adj_rev[v].push_back(u); } verts = std::stack<int>(); std::memset(vis, 0, sizeof(vis)); for (int u = 1; u <= n; ++u) { dfs(u); } for (int i = 1; i <= n; ++i) { scc[i].clear(); } scc_cnt = 0; std::memset(vis, 0, sizeof(vis)); while (verts.size() > 0) { int u = verts.top(); if (vis[u] == false) { scc_cnt++; dfs_rev(u); } verts.pop(); } std::memset(is_in_path, 0, sizeof(is_in_path)); for (int u = 1; u <= n; ++u) { is_in_path[scc_id[path[u]]] = true; } for (int i = 1; i <= scc_cnt; ++i) { scc_adj[i].clear(); } for (int u = 1; u <= n; ++u) { for (int v : adj[u]) { if (scc_id[u] != scc_id[v]) { scc_adj[scc_id[u]].push_back(scc_id[v]); } } } for (int i = 1; i <= scc_cnt; ++i) { std::sort(scc_adj[i].begin(), scc_adj[i].end()); scc_adj[i].erase(std::unique(scc_adj[i].begin(), scc_adj[i].end()), scc_adj[i].end()); } dt = 0; scc_topo_verts = std::stack<int>(); std::memset(vis, 0, sizeof(vis)); for (int i = 1; i <= scc_cnt; ++i) { dfs_scc_topo(i); } std::sort(path + 1, path + k + 1, [](int u, int v) { int u_scc_id = scc_id[u]; int v_scc_id = scc_id[v]; if (u_scc_id != v_scc_id) { return scc_topo_pos[u_scc_id] > scc_topo_pos[v_scc_id]; } return u < v; }); std::memset(vis, 0, sizeof(vis)); bool possible = true; for (int i = 1; i < k; ++i) { int u = path[i]; int v = path[i + 1]; int u_scc_id = scc_id[u]; int v_scc_id = scc_id[v]; if (u_scc_id != v_scc_id) { if (is_reachable(u_scc_id, v_scc_id) == false) { possible = false; break; } } } if (possible) { for (int i = 1; i <= k; ++i) { std::cout << path[i] << ' '; } std::cout << '\n'; } else { std::cout << -1 << '\n'; } } }