OI XXXIII - wyk

// https://szkopul.edu.pl/problemset/problem/gXVOzwn9b8K6dXwGJMDCbqX_/site/?key=statement

// Wykaz dróg

#include <bits/stdc++.h>

constexpr int sizik = 1501;
#define ar std::array
int n, m;

namespace brut1 {

void solve() {
    int wyn = n * (n - 1);
    wyn /= 2;
    wyn += n - 1;

    std::cout << wyn << '\n';

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            std::cout << i << " " << j << '\n';
        }
    }
    for (int i = n - 1; i >= 1; i--) {
        std::cout << n << " " << i << '\n';
    }
}

} // namespace brut1

namespace brut3 {

std::vector<int> kra[sizik];
std::vector<int> kra1[sizik];
std::vector<int> kra_sss[sizik];

std::bitset<sizik> dd1[sizik];
int curr = 1;

std::vector<int> post;
std::vector<int> topo;

int visited[sizik];
void DFS1(int v) {
    if (visited[v] == curr) return;
    visited[v] = curr;
    for (const auto& u : kra[v]) {
        DFS1(u);
    }
    post.push_back(v);
}

int sss_num[sizik];
int curr_sss;
std::vector<int> sss[sizik];

void DFS2(int v) {
    if (visited[v] == curr) return;
    visited[v] = curr;
    sss_num[v] = curr_sss;
    sss[curr_sss].push_back(v);
    for (const auto& u : kra1[v]) {
        DFS2(u);
    }
}

void DFS3(int v) {
    if (visited[v] == curr) {
        return;
    }

    visited[v] = curr;
    for (const auto& u : kra_sss[v]) {
        DFS3(u);
    }
    topo.push_back(v);
}

std::vector<std::pair<int, int>> ans;

void solve() {
    for (int i = 1; i <= m; i++) {
        int a, b;
        std::cin >> a >> b;

        kra[a].push_back(b);
        kra1[b].push_back(a);
    }

    ans.reserve(n * n);

    curr++;
    for (int i = 1; i <= n; i++) {
        if (visited[i] != curr) {
            DFS1(i);
        }
    }

    std::reverse(post.begin(), post.end());

    curr++;
    for (const auto& a : post) {
        if (visited[a] != curr) {
            curr_sss++;
            DFS2(a);
        }
    }

    post.clear();
    post.shrink_to_fit();

    for (int i = 1; i <= n; i++) {
        for (const auto& x : kra[i]) {
            kra_sss[sss_num[i]].push_back(sss_num[x]);
        }
    }

    curr++;
    for (int i = 1; i <= curr_sss; i++) {
        if (visited[i] != curr) {
            DFS3(i);
        }
    }

    std::reverse(topo.begin(), topo.end());

    for (int i = topo.size() - 1; i >= 0; i--) {
        int u = topo[i];
        dd1[u][u] = true;
        for (const auto& v : kra_sss[u]) {
            dd1[u] |= dd1[v];
        }
    }
    for (int i = 0; i < topo.size(); i++) {
        for (int j = topo.size() - 1; j > i; j--) {
            if (!dd1[topo[i]][topo[j]]) {
                ans.push_back({sss[topo[i]][0], sss[topo[j]][0]});
            }
        }
    }

    for (int i = topo.size() - 2; i >= 0; i--) {
        ans.push_back({sss[topo.back()][0], sss[topo[i]][0]});
    }

    std::cout << ans.size() << '\n';
    for (const auto& [a, b] : ans) {
        std::cout << a << " " << b << '\n';
    }
}

} // namespace brut3

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n >> m;

    if (m == 0) {
        brut1::solve();
        return 0;
    }

    brut3::solve();

    return 0;
}