#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
// Structure to handle Disjoint Set Union (DSU) logic
struct DSU {
vector<int> parent;
DSU(int n) {
parent.assign(n, -1);
}
int find_root(int v) {
if (parent[v] < 0) return v;
return parent[v] = find_root(parent[v]);
}
bool unite(int child, int parent_node) {
int root_child = find_root(child);
int root_parent = find_root(parent_node);
// If they are already in the same component, adding this edge creates a cycle
if (root_child == root_parent) return false;
// In this specific problem, we treat the 'parent_node' as the new representative
parent[root_child] = root_parent;
return true;
}
};
// Global variables for graph state
vector<int> good_edges[300005];
set<int> forbidden_targets[300005];
set<int> unvisited_components;
void build_tree(int current_node, vector<pair<int, int>>& result_edges) {
unvisited_components.erase(current_node);
vector<int> children_to_process;
// 1. Try to connect other component roots to this node
auto it = unvisited_components.begin();
while (it != unvisited_components.end()) {
int candidate = *it;
// Check if the edge (candidate -> current_node) is forbidden
if (forbidden_targets[candidate].find(current_node) == forbidden_targets[candidate].end()) {
children_to_process.push_back(candidate);
// Remove from set immediately so other branches don't try to grab it
it = unvisited_components.erase(it);
} else {
++it;
}
}
// 2. Add the pre-existing 'good' edges that point to this node
for (int neighbor : good_edges[current_node]) {
children_to_process.push_back(neighbor);
unvisited_components.erase(neighbor);
}
// 3. Record these edges and recurse
for (int child : children_to_process) {
result_edges.push_back({child, current_node});
}
for (int child : children_to_process) {
build_tree(child, result_edges);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
if (!(cin >> n >> m >> k)) return 0;
DSU dsu(n);
vector<bool> has_outgoing_edge(n, false);
// Process required edges
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
good_edges[v].push_back(u);
// A node can only have one outgoing edge in this tree
if (has_outgoing_edge[u] || !dsu.unite(u, v)) {
cout << "NO" << endl;
return 0;
}
has_outgoing_edge[u] = true;
}
// Process forbidden pairs
for (int i = 0; i < k; ++i) {
int u, v;
cin >> u >> v;
forbidden_targets[u].insert(v);
}
// Identify roots of existing components
vector<int> component_roots;
for (int i = 0; i < n; ++i) {
if (dsu.parent[i] < 0) {
component_roots.push_back(i);
}
}
// First Pass: Find a valid root for the entire tree
for (int root : component_roots) unvisited_components.insert(root);
vector<pair<int, int>> temp_edges;
int final_root = -1;
for (int root : component_roots) {
if (unvisited_components.count(root)) {
final_root = root;
build_tree(root, temp_edges);
}
}
// Second Pass: Build the final tree from that root
unvisited_components.clear();
for (int root : component_roots) unvisited_components.insert(root);
vector<pair<int, int>> final_edges;
build_tree(final_root, final_edges);
// Final Validation
if (final_edges.size() != (size_t)n - 1) {
cout << "NO" << endl;
} else {
for (auto& edge : final_edges) {
cout << edge.first << " " << edge.second << "\n";
}
}
return 0;
}
