#include #include #include #include #include #include #include #include using namespace std; typedef vector > Graph; vector tsort(Graph G, int start, int end) { vector ret; int degree[end]; memset(degree, 0, sizeof(degree)); for (int from = start; from < end; from++) { for (int i = 0; i < G[from].size(); i++) { int to = G[from][i]; degree[to]++; } } stack root; for (int i = start; i < end; i++) { if (degree[i] == 0) { root.push(i); } } while (!root.empty()) { int from = root.top(); root.pop(); ret.push_back(from); for (int i = 0; i < G[from].size(); i++) { int to = G[from][i]; degree[to]--; if (degree[to] == 0) { root.push(to); } } } return ret; } int main() { int N, M; cin >> N >> M; vector U; vector V; Graph BG(N); Graph OG(N); Graph DG(N); int u, v; for (int i = 0; i < M; ++i) { cin >> u >> v; --u; --v; U.push_back(u); V.push_back(v); BG[u].push_back(v); } vector A; vector B; map> SL; bool visited[N]; memset(visited, false, sizeof(visited)); for (int v = 0; v < N; ++v) { if (visited[v]) continue; bool checked[N]; memset(checked, false, sizeof(checked)); queue que; que.push(v); while (not que.empty()) { int x = que.front(); que.pop(); if (visited[x]) continue; visited[x] = true; checked[x] = true; for (int u : BG[x]) { if (checked[u]) { fprintf(stderr, "skip: x: %d, u: %d\n", x + 1, u + 1); A.push_back(x); B.push_back(u); SL[x].insert(u); } else if (visited[u]) { // NOOP } else { que.push(u); } } } } for (int i = 0; i < M; ++i) { int u = U[i]; int v = V[i]; if (SL[u].find(v) != SL[u].end()) continue; DG[u].push_back(v); OG[u].push_back(v); OG[v].push_back(u); } bool checked[N]; memset(checked, false, sizeof(checked)); for (int v = 0; v < N; ++v) { if (checked[v]) continue; queue que; que.push(v); int id = 0; map mapping; map r_mapping; vector vs; while (not que.empty()) { int x = que.front(); que.pop(); if (checked[x]) continue; checked[x] = true; mapping[x] = id; r_mapping[id] = x; id++; vs.push_back(x); for (int u : OG[x]) { if (checked[u]) continue; que.push(u); } } int n = vs.size(); if (n >= 2) { fprintf(stderr, "n: %d\n", n); Graph G(n); for (int x : vs) { int from = mapping[x]; for (int u : DG[x]) { int to = mapping[u]; G[from].push_back(to); } } vector res = tsort(G, 0, n); if (res.size() != n) { for (int x : vs) { for (int u : G[mapping[x]]) { fprintf(stderr, "x: %d, u: %d\n", x + 1, r_mapping[u] + 1); } } } int k = res.size() - 1; for (int i = 0; i < k; ++i) { int a = res[i]; int b = res[i + 1]; a = r_mapping[a]; b = r_mapping[b]; A.push_back(a); B.push_back(b); } assert(res.size() == n); } } int K = A.size(); cout << K << endl; for (int i = 0; i < K; ++i) { cout << A[i] + 1 << " " << B[i] + 1 << endl; } return 0; }