acm.mipt.ru 098s2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <ctime>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
#define pii pair<int,int>
const int maxm = 200001;
const int maxn = 20001;
vector<int> g[maxn], gi[maxn], order, g2[maxn];
int comp[maxn], used[maxn], L[maxm], R[maxm], ver[maxn], in[maxn], out[maxn], cc, n, m, sl[maxn+10], timer;
int tin[maxn], tout[maxn];
vector<pii> ans;


void Dfs1(int v) {

    comp[v] = true;

    forit(it, g[v]) {
        int to = *it;
        if (!comp[to]) Dfs1(to);
    }

    order.pb(v);
}

void Dfs2(int v) {

    comp[v] = cc;
    ver[cc] = v;

    forit(it, gi[v]) {
        int to = *it;
        if (!comp[to]) Dfs2(to);
    }
}

void Dfs3(int v) {

    tin[v] = ++timer;
    used[v] = 1;

    forit(it, g2[v]) {
        int to = *it;

        if (!used[to]) Dfs3(to);
        else {
            sl[tin[to]] = -1;
            sl[tout[to]] = -2;
        }
    }

    tout[v] = ++timer;
}

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].pb(v);
        gi[v].pb(u);
        L[i] = u; R[i] = v;
    }

    for (int i = 0; i < n; ++i)
        if (!comp[i]) Dfs1(i);

    memset(comp, 0, sizeof(comp));
    for (int i = (int)order.size() - 1; i >= 0; --i)
        if (!comp[order[i]]) {
            cc++;
            Dfs2(order[i]);
        }

    if (cc == 1) {
        puts("0");
        return 0;
    }

    for (int i = 0; i < m; ++i) {
        int u = L[i], v = R[i];

        if (comp[u] != comp[v]) {
            g2[comp[u]].pb(comp[v]);
            in[comp[v]] = true;
            out[comp[u]] = true;
        }
    }


    vector<int>  S, T;

    for (int i = 1; i <= cc; ++i) {
        if (!in[i]) S.pb(i);
        if (!out[i]) T.pb(i);
    }

    int anscnt = max(S.size(), T.size());

//  cerr <<" ans = " << anscnt << endl;

    memset(used, 0, sizeof(used));

    forit (it1, S) {

        int s = *it1;

        memset(sl, 0, sizeof(sl));

        Dfs3(s);

        forit(it2, T) {
            int t = *it2;
            if (!out[t] && !used[t]) {

                ans.pb(mp(ver[t], ver[s]));
                g2[t].pb(s);
                out[t] = true;
                in[s] = true;
                break;
            }
        }

        if (in[s]) continue;

        sl[tin[s]] = -1;
        sl[tout[s]] = -2;

        forit (it, T) {
            if (!sl[tin[*it]])
                sl[tin[*it]] = *it;
        }

        int op = 0;
        for (int j = 1; j <= timer; ++j) {

            if (sl[j] == -1) op++; else
            if (sl[j] == -2) op--; else
            if (sl[j] != 0 && op == 0) {
                ans.pb(mp(ver[sl[j]], ver[s]));
                g2[sl[j]].pb(s);
                in[s] = true;
                out[sl[j]] = true;
                break;
            }
        }
    }
/*  puts("begin");
    forit(it, ans) {
        cout << it -> f << " "<<it -> s << endl;
    }
    puts("end");
     */
    int i = 0, j = 0;
    while (i < S.size() && j < T.size()) {

        while (i < S.size() && in[S[i]]) i++;
        while (j < T.size() && out[T[j]]) j++;

        if (i < S.size() && j < T.size()) {
            ans.pb(mp(ver[T[j]], ver[S[i]]));
            in[S[i]] = true;
            out[T[j]] = true;
        }
    }

    int v = -1;
    if (T.empty()) v = 0; else
    v = ver[T[0]];



    while (i < S.size()) {

        if (!in[S[i]]) ans.pb(mp(v, ver[S[i]]));
        i++;
    }

    if (S.empty()) v = 0; else
    v = ver[S[0]];

    while (j < T.size()) {

        if (!out[T[j]]) ans.pb(mp(ver[T[j]], v));
        ++j;
    }


    assert(ans.size() == anscnt);
    printf("%d\n", ans.size());
    forit(it, ans) {
        printf("%d %d\n", it -> f, it -> s);
    }

    return 0;
}