#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
// parent[u] = v means good edge u->v exists, i.e. u sends garbage to v
// In the final tree every node except root has out-degree 1 (edge toward root).
vector<int> parent(n, -1); // parent from good edges
vector<vector<int>> children(n); // reverse of good edges (for tree traversal)
// Read good edges
vector<pair<int,int>> good_edges(m);
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
good_edges[i] = {a, b};
// edge a -> b means a sends to b, so parent[a] = b
if(parent[a] != -1){
// node a already has an outgoing good edge -> out-degree > 1 -> impossible
cout << "NO\n";
return 0;
}
parent[a] = b;
children[b].push_back(a);
}
// Check good edges form a forest (no cycles)
// Use union-find
vector<int> uf(n);
iota(uf.begin(), uf.end(), 0);
vector<int> uf_rank(n, 0);
function<int(int)> find = [&](int x) -> int {
while(uf[x] != x) x = uf[x] = uf[uf[x]];
return x;
};
auto unite = [&](int a, int b) -> bool {
a = find(a); b = find(b);
if(a == b) return false;
if(uf_rank[a] < uf_rank[b]) swap(a, b);
uf[b] = a;
if(uf_rank[a] == uf_rank[b]) uf_rank[a]++;
return true;
};
for(auto& [a, b] : good_edges){
if(!unite(a, b)){
// cycle detected
cout << "NO\n";
return 0;
}
}
// Find root of each tree in the forest
// root of tree containing node u: follow parent[] until -1
// But this could be slow. Instead, roots are nodes with parent[u] == -1
// that are the "top" of their tree. But we also need to know which tree
// each node belongs to, and the root of that tree.
// tree_root[u] = the root of the forest-tree containing u
// We find it by following parent pointers up (iteratively to avoid stack overflow).
vector<int> tree_root(n, -1);
for(int i = 0; i < n; i++){
if(tree_root[i] != -1) continue;
// Follow parent chain to find root, collecting nodes along the way
vector<int> path;
int cur = i;
while(cur != -1 && tree_root[cur] == -1){
path.push_back(cur);
if(parent[cur] == -1){
// cur is a root
tree_root[cur] = cur;
break;
}
cur = parent[cur];
}
// Now cur either has tree_root set, or we reached a root
int root_val = (cur != -1) ? tree_root[cur] : tree_root[path.back()];
for(int x : path) tree_root[x] = root_val;
}
// Collect all tree roots
vector<int> roots;
for(int i = 0; i < n; i++){
if(parent[i] == -1) roots.push_back(i);
}
// Read forbidden edges
// forbidden: set of (u, v) meaning we cannot build edge u -> v
unordered_set<long long> forbidden;
auto encode = [&](int u, int v) -> long long {
return (long long)u * n + v;
};
for(int i = 0; i < k; i++){
int c, d;
cin >> c >> d;
forbidden.insert(encode(c, d));
}
// Also, good edges that already exist should be treated as taken,
// and we should not create duplicate edges. But the problem says
// "All of the M+K ordered pairs in the input will be distinct."
// However, we also need to avoid self-loops and edges within the same tree
// that would create cycles. Actually, the tree structure handles this:
// we only add edges from tree roots to nodes in other trees.
// Now we need to build a full arborescence.
// Strategy from editorial:
// - Consider the forest of good edges. We need to connect tree roots
// to nodes in other trees to form a single arborescence.
// - An edge from tree_root r to some node v (in another tree) means
// r -> v (r sends garbage to v), making v's tree the parent.
// - We use the Kosaraju-like trick:
// Phase 1: Run DFS from node 0's tree root. DFS visits nodes in the
// current tree (following children[] edges in reverse), and at each
// visited node, tries to connect unconnected tree roots.
// If not all trees connected, pick an unconnected tree root and continue.
// Remember the last starting tree root.
// Phase 2: Run DFS again from the last starting tree root (reset visited).
// If it connects everything, output the solution. Otherwise, NO.
// Implementation details:
// We maintain a set of "unconnected tree roots".
// When we visit a node v during DFS, we try to connect each unconnected
// tree root r to v: this means adding edge r -> v. We need:
// 1. r != tree_root[v] (different tree)
// 2. (r, v) not forbidden
// If we succeed, we remove r from unconnected set and DFS into r's tree.
// To efficiently iterate over unconnected roots and skip forbidden ones:
// Keep unconnected roots in a set. For each visited node v, iterate
// over unconnected roots and try to connect. If forbidden, skip.
// The key insight from editorial: total work is O(N + K) because each
// successful connection removes a root (O(N) total), and each failed
// attempt corresponds to a forbidden edge (O(K) total).
int num_trees = roots.size();
if(num_trees == 1){
// Already a single tree, just output good edges
for(auto& [a, b] : good_edges){
cout << a << " " << b << "\n";
}
return 0;
}
// We need to add num_trees - 1 new edges connecting tree roots to other nodes.
// Plus the original M good edges.
// Total should be N-1 edges.
// DFS function: visits nodes within their tree (using children[] edges),
// and at each node tries to connect unconnected tree roots.
// Returns list of new edges added.
auto solve = [&](int start_root) -> pair<bool, vector<pair<int,int>>> {
// start_root is a tree root from which we begin
vector<bool> visited(n, false);
vector<pair<int,int>> new_edges;
set<int> unconnected; // set of tree roots not yet connected
for(int r : roots){
if(r != start_root) unconnected.insert(r);
}
// DFS stack: we visit nodes and traverse children[] edges (within tree)
// plus newly connected tree roots
stack<int> stk;
// Visit all nodes in start_root's tree first
stk.push(start_root);
visited[start_root] = true;
while(!stk.empty()){
int v = stk.top();
stk.pop();
// Try to connect unconnected tree roots to v
// We iterate over unconnected and try edge (r, v)
// Must skip if forbidden
vector<int> to_connect;
vector<int> still_unconnected;
// We need to be careful: iterate and collect
auto it = unconnected.begin();
while(it != unconnected.end()){
int r = *it;
if(!forbidden.count(encode(r, v))){
to_connect.push_back(r);
it = unconnected.erase(it);
} else {
++it;
}
}
for(int r : to_connect){
new_edges.push_back({r, v});
// Now DFS into r's tree
stk.push(r);
visited[r] = true;
}
// Also visit children of v within its own tree
for(int c : children[v]){
if(!visited[c]){
visited[c] = true;
stk.push(c);
}
}
}
if(unconnected.empty()){
return {true, new_edges};
}
return {false, {}};
};
// Phase 1: Kosaraju-like approach
// Run DFS from each unvisited tree root, tracking the last one
{
vector<bool> tree_visited(n, false); // which trees have been visited
// We track visited by tree root
set<int> unconnected_roots(roots.begin(), roots.end());
int last_start = -1;
// Start from root 0's tree root
// Actually, start from roots[0]
// We do the Kosaraju-like iteration:
// Pick an unvisited tree root, DFS from it (connecting what we can),
// repeat until all trees visited. The last starting root is the candidate.
// But we need to be more careful. The editorial says:
// Run DFS from v0=0. If not all visited, run from some unvisited v1, etc.
// The last starting node vk is the candidate root.
// Then verify by running DFS from vk again.
// For Phase 1, we don't need to track new edges, just find the candidate.
// Let's do a simplified version.
vector<bool> visited(n, false);
set<int> remaining_roots(roots.begin(), roots.end());
// Start from the tree root of node 0
int first = tree_root[0];
last_start = first;
remaining_roots.erase(first);
// DFS from first
stack<int> stk;
stk.push(first);
visited[first] = true;
while(!remaining_roots.empty()){
// Process DFS stack
while(!stk.empty()){
int v = stk.top();
stk.pop();
// Try to connect remaining roots to v
auto it = remaining_roots.begin();
while(it != remaining_roots.end()){
int r = *it;
if(!forbidden.count(encode(r, v))){
// Can connect r -> v
it = remaining_roots.erase(it);
stk.push(r);
visited[r] = true;
} else {
++it;
}
}
// Visit children within tree
for(int c : children[v]){
if(!visited[c]){
visited[c] = true;
stk.push(c);
}
}
}
if(!remaining_roots.empty()){
// Pick a remaining root and start DFS from it
int r = *remaining_roots.begin();
remaining_roots.erase(remaining_roots.begin());
last_start = r;
stk.push(r);
visited[r] = true;
}
}
// Phase 2: Try DFS from last_start
auto [ok, new_edges] = solve(last_start);
if(ok){
for(auto& [a, b] : good_edges){
cout << a << " " << b << "\n";
}
for(auto& [a, b] : new_edges){
cout << a << " " << b << "\n";
}
} else {
cout << "NO\n";
}
}
return 0;
}
