// Utilities library #include <cstdlib> #include <bitset> #include <functional> #include <utility> #include <tuple> #include <limits> #include <cinttypes> #include <cassert> // Strings library #include <cctype> #include <cstring> #include <string> // Containers library #include <array> #include <vector> #include <deque> #include <list> #include <forward_list> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <stack> #include <queue> // Algorithms library #include <algorithm> // Iterators library #include <iterator> // Numerics library #include <cmath> #include <complex> #include <valarray> #include <numeric> // Input/Ouput library #include <iostream> #include <sstream> #include <iomanip> #include <cstdio> // Localization library #include <locale> // Regular expressions library #include <regex> template <typename T> static T input(std::istream &is = std::cin) { T value; is >> value; return value; } template <typename Function> static void repeat(std::size_t n, Function f) { while (n--) f(); } // Program code class directed_graph { std::vector<std::vector<size_t>> outedges, inedges; std::vector<std::pair<size_t, size_t>> edge_list; public: directed_graph(size_t n_verts) : outedges(n_verts), inedges(n_verts) {} size_t add_edge(size_t src, size_t tgt) { edge_list.emplace_back(src, tgt); const size_t edge_id = edge_list.size() - 1; outedges[src].push_back(edge_id); inedges[tgt].push_back(edge_id); return edge_id; } size_t num_vertices() const { return outedges.size(); } size_t num_edges() const { return edge_list.size(); } size_t source(size_t e) const { return edge_list[e].first; } size_t target(size_t e) const { return edge_list[e].second; } const std::vector<size_t> &out_edges(size_t v) const { return outedges[v]; } const std::vector<size_t> &in_edges(size_t v) const { return inedges[v]; } size_t out_degree(size_t v) const { return outedges[v].size(); } size_t in_degree(size_t v) const { return inedges[v].size(); } }; template <typename Graph> size_t strong_components(const Graph &g, std::vector<size_t> &comp) { const size_t num_vertices = g.num_vertices(); size_t time = 0; size_t comp_cnt = 0; std::stack<size_t> S; std::vector<size_t> low(num_vertices); std::vector<size_t> dtm(num_vertices); comp.resize(num_vertices); std::function<void(size_t)> dfs_visit; dfs_visit = [&](const size_t v) { low[v] = dtm[v] = ++time; comp[v] = SIZE_MAX; S.push(v); for (const auto edge : g.out_edges(v)) { const size_t w = g.target(edge); if (!dtm[w]) { dfs_visit(w); low[v] = std::min(low[v], low[w]); } else if (comp[w] == SIZE_MAX) low[v] = std::min(low[v], dtm[w]); } if (dtm[v] != low[v]) return; size_t w; do { w = S.top(), S.pop(); comp[w] = comp_cnt; } while (w != v); ++comp_cnt; }; for (size_t v = 0; v != num_vertices; ++v) if (!dtm[v]) dfs_visit(v); return comp_cnt; } directed_graph make_condesate(const directed_graph &g, const std::vector<size_t> &comp, const size_t num_comps) { directed_graph cg(num_comps); for (size_t e = 0; e != g.num_edges(); ++e) { const size_t src = comp[g.source(e)]; const size_t tgt = comp[g.target(e)]; if (src != tgt) cg.add_edge(src, tgt); } return cg; } bool has_solution(const directed_graph &cg, const std::vector<size_t> &comp, const std::vector<size_t> &target_cities) { std::vector<bool> has_targets(cg.num_vertices()); for (const auto v : target_cities) has_targets[comp[v]] = true; const size_t num_vertices = cg.num_vertices(); const size_t num_edges = cg.num_edges(); std::queue<size_t> Q; std::vector<size_t> in_degree(num_vertices); for (size_t e = 0; e != num_edges; ++e) ++in_degree[cg.target(e)]; size_t num_targets = 0; for (size_t v = 0; v != num_vertices; ++v) if (!in_degree[v]) { Q.push(v); if (has_targets[v]) ++num_targets; } while (!Q.empty()) { const size_t src = Q.front(); Q.pop(); if (num_targets > 1) return false; if (has_targets[src]) --num_targets; for (const auto e : cg.out_edges(src)) { const auto tgt = cg.target(e); --in_degree[tgt]; if (!in_degree[tgt]) { Q.push(tgt); if (has_targets[tgt]) ++num_targets; } } // end for out-edges } return true; } std::vector<long> find_solution(const directed_graph &g, const std::vector<size_t> &target_cities) { std::vector<size_t> comp; const size_t num_comps = strong_components(g, comp); const auto cg = make_condesate(g, comp, num_comps); if (!has_solution(cg, comp, target_cities)) return {-1}; std::vector<std::vector<size_t>> order(num_comps); for (const size_t v : target_cities) order[comp[v]].push_back(v); std::vector<long> solution; solution.reserve(target_cities.size()); std::for_each(order.rbegin(), order.rend(), [&](std::vector<size_t> &vec) { std::sort(vec.begin(), vec.end()); for (const auto elem : vec) solution.push_back(elem + 1); }); return solution; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); repeat(input<size_t>(), [&] { const auto num_vertices = input<size_t>(); const auto num_edges = input<size_t>(); const auto K = input<size_t>(); directed_graph g(num_vertices); std::vector<size_t> target_cities(K); for (auto &city : target_cities) city = input<size_t>() - 1; repeat(num_edges, [&] { const auto src = input<size_t>() - 1; const auto tgt = input<size_t>() - 1; g.add_edge(src, tgt); }); const auto sol = find_solution(g, target_cities); for (const auto cx : sol) std::cout << cx << ' '; std::cout << '\n'; }); }