#include <bits/stdc++.h>
using namespace std;
int main(){
int N, M, K;
scanf("%d%d%d", &N, &M, &K);
vector<int> par(N, -1);
vector<vector<int>> ch(N);
vector<pair<int,int>> gedges;
for(int i = 0; i < M; i++){
int a, b;
scanf("%d%d", &a, &b);
gedges.push_back({a, b});
// Each node can have at most one outgoing good edge
if(par[a] != -1){
puts("NO");
return 0;
}
par[a] = b;
ch[b].push_back(a);
}
// Check acyclicity with union-find
vector<int> uf(N);
iota(uf.begin(), uf.end(), 0);
auto find = [&](int x){
while(uf[x] != x) x = uf[x] = uf[uf[x]];
return x;
};
for(auto &[a, b] : gedges){
int fa = find(a), fb = find(b);
if(fa == fb){
puts("NO");
return 0;
}
uf[fa] = fb;
}
// Identify tree roots (nodes with no outgoing good edge)
vector<int> roots;
for(int i = 0; i < N; i++)
if(par[i] == -1)
roots.push_back(i);
// Single tree already — just output good edges
if((int)roots.size() == 1){
for(auto &[a, b] : gedges)
printf("%d %d\n", a, b);
return 0;
}
// Read forbidden edges into hash set
unordered_set<long long> forb;
forb.reserve(K * 2);
for(int i = 0; i < K; i++){
int c, d;
scanf("%d%d", &c, &d);
forb.insert((long long)c * N + d);
}
auto bad = [&](int u, int v) -> bool {
return forb.count((long long)u * N + v);
};
// Helper: DFS visiting all nodes of connected trees,
// connecting unattached tree roots via non-forbidden edges.
// When a root r is connected to node v, edge (r,v) is added
// and r's subtree is explored next.
auto sweep = [&](int start, set<int> &pool, vector<pair<int,int>> *out) {
pool.erase(start);
queue<int> tq; // queue of tree-roots whose subtrees to explore
tq.push(start);
while(!tq.empty()){
int tr = tq.front(); tq.pop();
stack<int> stk;
stk.push(tr);
while(!stk.empty()){
int v = stk.top(); stk.pop();
// Try attaching every remaining root to v
auto it = pool.begin();
while(it != pool.end()){
int r = *it;
if(!bad(r, v)){
if(out) out->push_back({r, v});
it = pool.erase(it);
tq.push(r);
} else {
++it;
}
}
for(int c : ch[v]) stk.push(c);
}
}
};
// Phase 1: Kosaraju-like — find candidate root.
// Run successive sweeps; the last starting root is the candidate.
int candidate = -1;
{
set<int> unvis(roots.begin(), roots.end());
vector<bool> vis(N, false);
for(int r : roots){
if(!vis[r]){
candidate = r;
vis[r] = true;
// Mark all roots reached from r as visited
set<int> pool;
for(auto it = unvis.begin(); it != unvis.end(); ){
if(*it == r){ it = unvis.erase(it); }
else { pool.insert(*it); ++it; }
}
// sweep connects roots from pool; we don't need edges yet
sweep(r, pool, nullptr);
// Remaining in pool are unvisited; put back
// But those reached are gone from pool; mark visited
for(int x : roots){
if(!vis[x] && pool.find(x) == pool.end()){
// x was in pool but got removed => reached
// Actually this logic is getting complicated.
// Let me redo phase 1 more simply.
}
}
// Hmm, let me redo this.
break; // will redo below
}
}
}// Cleaner Phase 1
candidate = -1;
{
set<int> unvis(roots.begin(), roots.end());
// We'll track which roots have been "visited" (reached by some sweep)
// by removing them from unvis.
// Successive sweeps: pick any unvisited root, sweep from it.
// The last root picked is the candidate.
while(!unvis.empty()){
int start = *unvis.begin();
candidate = start;
// sweep removes reachable roots from unvis
// but sweep's pool should be unvis minus start
// Actually sweep erases start and connected ones from pool.
// Let's just pass unvis directly:
sweep(start, unvis, nullptr);
// start and everything reachable from it via complement edges
// have been removed from unvis.
}
}
// Phase 2: Build tree from candidate
{
set<int> unconn(roots.begin(), roots.end());
vector<pair<int,int>> nedges;
sweep(candidate, unconn, &nedges);
if(!unconn.empty()){
puts("NO");
return 0;
}
for(auto &[a, b] : gedges)
printf("%d %d\n", a, b);
for(auto &[a, b] : nedges)
printf("%d %d\n", a, b);
}
return 0;
}
