[CSES] Building Roads

const ll N = 1e5 + 2;
ll sz[N], p[N];
void make_set(ll node) {
    p[node] = node;
    sz[node] = 1;
}

ll find_set(ll a) {
    if (p[a] == a) return p[a];
    return p[a] = find_set(p[a]);
}

void union_set(ll a, ll b) {
    a = find_set(a), b = find_set(b);
    if (a == b) return;

    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    p[b] = a;
}

void solve() {
    ll n, m;
    cin >> n >> m;

    rep(i, n) make_set(i);
    rep(i, m) {
        ll x, y;
        cin >> x >> y;
        --x, --y;
        union_set(x, y);
    }

    set<ll> p;
    rep(i, n) p.insert(find_set(i));

    cout << sz(p) - 1 << "\n";
    ll st = *p.begin();
    p.erase(p.begin());
    for (auto& x : p) cout << st + 1 << " " << x + 1 << "\n";
}