#include struct RNG { void setSeed(uint64_t seed) { seedSet = true; x = seed; } template T choice(std::vector& v) { assert(!v.empty()); return v[range(0, (int)v.size() - 1)]; } template void shuffle(std::vector& v) { const int N = v.size(); for (int i = 0; i < N - 1; i++) { const int j = range(i, N - 1); if (i == j) continue; std::swap(v[i], v[j]); } } // generate random integers in [from, to] template typename std::common_type::type range(T from, U to) { static_assert(std::is_integral_v); static_assert(std::is_integral_v); static_assert(std::is_integral_v::type>); assert(from <= to); uint64_t width = to - from + 1; typename std::common_type::type ret = from; ret += xorshift64() % width; return ret; } private: bool seedSet = false; uint64_t x; uint64_t xorshift64() { assert(seedSet); x ^= x << 13; x ^= x >> 7; x ^= x << 17; return x; } } rng; // 辺を 1 箇所張り替えて非連結にする using namespace std; //----NokonoKotlin library : UnionFind(n) , nは要素数----- class UnionFind { private: vector par; public: int Size; vector rank; // rankが高いほど上の親である vector size; // 配列の中身は0 ~ N-1 UnionFind() {} UnionFind(long long N) : rank(N), size(N) { Size = N; par.resize(N); for (int i = 0; i < Size; i++) par[i] = i; for (int i = 0; i < Size; i++) rank[i] = 0; for (int i = 0; i < Size; i++) size[i] = 1; } ~UnionFind() { Release(); } void Release() { if (par.size() == 0) { return; } } int root(int x) { if (par[x] == x) return x; else { par[x] = root(par[x]); return par[x]; } } void unite(int x, int y) { int rx = root(x); int ry = root(y); int S = size[ry] + size[rx]; if (rx == ry) return; if (rank[rx] < rank[ry]) { par[rx] = ry; // rankの高い方を親にする size[rx] = S; size[ry] = S; } else { par[ry] = rx; size[ry] = S; size[rx] = S; if (rank[rx] == rank[ry]) rank[rx]++; } } int getsize(int x) { return size[root(x)]; } bool same(int x, int y) { int rx = root(x); int ry = root(y); return rx == ry; } }; int main(int argc, char* argv[]) { rng.setSeed(372864312); int N = 100000; vector> edges; vector prufer(N - 1); for (int i = 0; i < N - 2; i++) prufer[i] = rng.range(1, N - 1); prufer.back() = N; multiset cands; for (int x = 1; x <= N; x++) cands.insert(x); for (int x : prufer) cands.erase(x); vector cnt(N + 1, 0); for (int x : prufer) cnt[x]++; for (int x : prufer) { int child = *cands.begin(); edges.emplace_back(x, child); cands.erase(child); cnt[x]--; if (cnt[x] == 0) cands.insert(x); } UnionFind T(N + 1); // どこかで切って 2 つの連結成分にする edges.erase(edges.begin() + int(edges.size()) / 2); for (auto p : edges) T.unite(p.first, p.second); cout << N << endl; // 片方をなもりグラフにして終了 for (int x = 1; x < N; x++) { for (int y = x + 1; y <= N; y++) { if (T.same(x, y)) { edges.emplace_back(x, y); for (pair p : edges) cout << min(p.first, p.second) << " " << max(p.first, p.second) << "\n"; return 0; } } } return 0; }