Авиаперелёты OK

#include <iostream>
#include <vector>
#include <set>

using namespace std;

vector<vector<int>> g, g_r;
vector<bool> used;
vector<int> order;
vector<int> component;

void dfs(int v) {
    used[v] = true;
    for (int i: g[v])
        if (!used[i])
            dfs(i);
    order.emplace_back(v);
}

void dfs_r(int v) {
    used[v] = true;
    component.push_back(v);
    for (int i: g_r[v])
        if (!used[i])
            dfs_r(i);
}


class Graph {
    vector<set<int>> g;
    vector<bool> used;

public:

    explicit Graph(int n) {
        g.resize(n);
        used.resize(n);
    }

    void set_graph(vector<set<int>> &_g) {
        g = _g;
    }

    vector<set<int>> get_graph() {
        return g;
    }

    int dfs_to_delete_edges(int v, int finish) {
        if (v == finish) {
            return 1;
        }
        used[v] = true;
        for (auto &i: g[v]) {
            if (!used[i]) {
                int res = dfs_to_delete_edges(i, finish);
                if (res)
                    return res + 1;
            }
        }
        return 0;
    }

    void exec() {
        for (auto & i : g) {

            // дфс в котором если находим ребро от стартовой до финишной вершины, и при этом у нас есть другие пути, то удаляем это ребро
            auto curr_copy = i;
            for (auto &k: curr_copy) { // будем смотреть сразу прямые рёбра, мы же их знаем
                bool is_path_not_1 = false;
                used.assign(used.size(), false);
                for (auto &j: i) {
                    if (!used[j]) {
                        int tmp = dfs_to_delete_edges(j, k);
                        if (tmp > 1) {
                            is_path_not_1 = true;
                            break;
                        }
                    }
                }
                // если нашлёлся путь длины больше 1, то удаляем это ребро
                if (is_path_not_1) {
                    i.erase(i.find(k));
                }
            }
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    used = vector<bool>(n);
    g = vector<vector<int>>(n);
    g_r = vector<vector<int>>(n);
    vector<pair<int, int>> edges(m);

    for (int i = 0; i < m; i++) {
        int fr, to;
        cin >> fr >> to;
        fr--;
        to--;
        g[fr].emplace_back(to);
        g_r[to].emplace_back(fr);
        edges[i] = make_pair(fr, to);
    }

    for (int i = 0; i < n; i++)
        if (!used[i])
            dfs(i);

    used = vector<bool>(n);

    vector<int> component_for_vertex(n, -1);
    vector<int> any_vertex_for_component;
    vector<pair<int, int>> answer;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int v = order[n - 1 - i];
        if (!used[v]) {
            dfs_r(v);
            any_vertex_for_component.emplace_back(component[0]);
            for (int j = 0; j < component.size() - 1; j++) {
                component_for_vertex[component[j]] = cnt;
                answer.emplace_back(component[j], component[j + 1]);
            }
            component_for_vertex[component[component.size() - 1]] = cnt;
            if (component.size() > 1)
                answer.emplace_back(component[component.size() - 1], component[0]);
            cnt++;
            component.clear();
        }
    }

    vector<set<int>> new_g(cnt);
    for (int i = 0; i < m; i++) {
        if (component_for_vertex[edges[i].first] != component_for_vertex[edges[i].second]) {
            // значит ребро между разными скс
            new_g[component_for_vertex[edges[i].first]].insert(component_for_vertex[edges[i].second]);
        }
    }

    // теперь работаем с деревом из скс
    Graph sks(cnt);
    sks.set_graph(new_g);
    sks.exec();
    new_g = sks.get_graph();

    for (int i = 0; i < new_g.size(); i++) {
        for (auto &j: new_g[i])
            answer.emplace_back(any_vertex_for_component[i], any_vertex_for_component[j]);
    }

    cout << answer.size() << '\n';
    for (auto &i: answer) {
        cout << i.first + 1 << ' ' << i.second + 1 << '\n';
    }

}