acm.mipt.ru 098s

#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)
const int maxm = 200001;
const int maxn = 20001;
vector<int> g[maxn], gi[maxn], order;
int comp[maxn], used[maxn], L[maxm], R[maxm], ver[maxn], in[maxn], out[maxn], cc, n, m;


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;

    int cnt = 0;
    forit(it, g2[v]) {
        int to = *it;
        if (!used[to]) {
            Dfs3(to);
            cnt++;
        } else
        if (used[to] == 2){
            sl[tin[to]] = -1;
            sl[tin[out]] = -2;
        }
    }

    if (cnt == 0) {
        T.pb(v);

    }

    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);
    }

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

    for (int i = 0; i < S.size(); ++i) {
        memset(sl, 0, sizeof(sl));

        Dfs3(S[i]);

        sl[tin[S[i]]] = -1;
        sl[tout[S[i]]] = -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++;
            if (sl[j] == -2) op--;

            if (sl[j] != 0 && op == 0) {
                ans.pb(mp(ver[sl[j]], ver[S[i]]));

                in[S[i]] = true;
                out[sl[j]] = true;
                break;
            }
        }


    }


    return 0;


}