可以证明本题答案上界为 $\mathcal{O}(n^2)$，通过下面的数据生成器可以快速的生成一组达到上界的数据：

#include "testlib.h"
#include <bits/stdc++.h>

int main(int argc, char *argv[]) {
    registerGen(argc, argv, 1);

    int const N = opt<int>("N", 1e5);
    int const M = N;
    int const L = opt<int>("L", N / 2);

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

    edges.emplace_back(1, 3);

    for (int i = 2; i <= L; ++i)
        edges.emplace_back(i - 1, i);

    for (int i = L + 1; i <= N; ++i)
        edges.emplace_back(L, i);

    shuffle(edges.begin(), edges.end());

    for (auto &iter : edges)
        if (rnd.next(0, 1))
            std::swap(iter.first, iter.second);

    shuffle(edges.begin(), edges.end());

    std::vector<int> id(N + 1);

    std::iota(id.begin(), id.end(), 0);

    shuffle(id.begin() + 1, id.end());

    for (auto &iter : edges) {
        iter.first = id[iter.first];
        iter.second = id[iter.second];
    }

    shuffle(edges.begin(), edges.end());

    std::cout << N << " " << M << std::endl;

    for (auto const &iter : edges)
        std::cout << iter.first << " " << iter.second << std::endl;
}

官方数据好像没有卡。