思路与算法

把每条第一类要求a能联系b直接作为a->b电话线。这个必须图最稀疏，且其边数m已经不超过允许上限n+m+t。只需判断必须图中是否有任何第二类禁达关系成立。先用显式栈进行两遍Kosaraju，把强连通分量缩成DAG。禁达的两端若在同一SCC内则直接矛盾；若拓扑次序反向则必不可达。其余要求按不同目标SCC分组，每次选至多512个目标，给目标置位，逆拓扑沿边把后继位集并入前驱，从源SCC相应位查询是否可达。有矛盾输出NO；全部无矛盾则输出去重后的第一类边作为YES构造。

正确性说明

任何满足第一类要求的图都必须具有必须图中每条边代表的可达关系，因此由可达关系的传递性，也必须具有必须图的全部可达关系。若必须图已有一条禁达关系，则任何合法候选都会违背它，故无解。反之若必须图不违背任何禁达要求，它本身显然满足全部第一类要求，且边数最多m，故是合法构造。缩点不改变不同SCC之间的可达性，同SCC内不同原点互相可达。对目标位集做逆拓扑递推，“u可达目标”恰当且仅当u自身为该目标或某个后继可达目标，归纳得到所有查询精确真值。分块只是分开保存目标，未使用有碰撞风险的哈希。

复杂度

SCC及邻接表初始化O(n+m)，DAG去重排序最坏O(m log m)。令C为SCC数、E为缩点后边数、U为待判不同目标数。每块512位即8个64位字，清零和传播O(8(C+E))，总O(n+m log m+t+8(C+E)ceil(U/512))，等价主项O((C+E)U/64)。空间O(n+m+t+8C)，不存C²位的完整闭包。

易错点

电话线可以有向且原要求可重复；输出去重即可，不能把有向图当无向图。第二类也可能与第一类同对或通过长路径冲突。不能只检查直接边。n=100000深链要使用迭代遍历，避免递归栈溢出。输出NO需要无解证据；YES允许任意满足关系且边数合限的网络，使用原生特判验全部正反关系。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
// Iterative Kosaraju followed by exact blocked reachability on the SCC DAG.
bool possible(int n, const vector<pair<int, int>> &edges, const vector<pair<int, int>> &bad) {
    vector<vector<int>> g(n), rg(n);
    for (auto e : edges) {
        g[e.first].push_back(e.second);
        rg[e.second].push_back(e.first);
    }
    vector<char> seen(n);
    vector<int> ord;
    for (int s = 0; s < n; s++)
        if (!seen[s]) {
            vector<pair<int, int>> st(1, {s, 0});
            seen[s] = 1;
            while (!st.empty()) {
                int u = st.back().first;
                int &i = st.back().second;
                if (i == (int)g[u].size()) {
                    ord.push_back(u);
                    st.pop_back();
                } else {
                    int v = g[u][i++];
                    if (!seen[v]) {
                        seen[v] = 1;
                        st.push_back({v, 0});
                    }
                }
            }
        }
    vector<int> co(n, -1);
    int C = 0;
    for (int i = n - 1; i >= 0; i--)
        if (co[ord[i]] < 0) {
            vector<int> st(1, ord[i]);
            co[ord[i]] = C;
            while (!st.empty()) {
                int u = st.back();
                st.pop_back();
                for (int v : rg[u])
                    if (co[v] < 0) {
                        co[v] = C;
                        st.push_back(v);
                    }
            }
            C++;
        }
    vector<vector<int>> dag(C), qs(C);
    vector<int> targets;
    for (auto e : edges)
        if (co[e.first] != co[e.second])
            dag[co[e.first]].push_back(co[e.second]);
    for (int u = 0; u < C; u++) {
        sort(dag[u].begin(), dag[u].end());
        dag[u].erase(unique(dag[u].begin(), dag[u].end()), dag[u].end());
    }
    for (auto e : bad) {
        int a = co[e.first], b = co[e.second];
        if (a == b)
            return false;
        if (a > b)
            continue;
        if (qs[b].empty())
            targets.push_back(b);
        qs[b].push_back(a);
    }
    const int W = 8;
    vector<array<unsigned long long, W>> bits(C);
    for (size_t off = 0; off < targets.size(); off += 512) {
        for (auto &a : bits)
            a.fill(0);
        size_t end = min(off + 512, targets.size());
        for (size_t j = off; j < end; j++)
            bits[targets[j]][(j - off) >> 6] |= 1ull << ((j - off) & 63);
        for (int u = C - 1; u >= 0; u--)
            for (int v : dag[u])
                for (int w = 0; w < W; w++)
                    bits[u][w] |= bits[v][w];
        for (size_t j = off; j < end; j++)
            for (int u : qs[targets[j]])
                if (bits[u][(j - off) >> 6] >> ((j - off) & 63) & 1)
                    return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, t;
    cin >> n >> m;
    vector<pair<int, int>> e(m);
    for (auto &x : e) {
        cin >> x.first >> x.second;
        --x.first;
        --x.second;
    }
    cin >> t;
    vector<pair<int, int>> bad(t);
    for (auto &x : bad) {
        cin >> x.first >> x.second;
        --x.first;
        --x.second;
    }
    if (!possible(n, e, bad)) {
        cout << "NO\n";
        return 0;
    }
    sort(e.begin(), e.end());
    e.erase(unique(e.begin(), e.end()), e.end());
    cout << "YES\n" << e.size() << '\n';
    for (auto x : e)
        cout << x.first + 1 << ' ' << x.second + 1 << '\n';
}