Connect cities

#include <bits/stdc++.h>
using namespace std;

#define all(x)  begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x)   (int)(x).size()                                 // signed size: avoids the unsigned .size() wrap bug

using ll  = long long;
using pii = pair<int,int>;
using vi  = vector<int>;

#ifdef LOCAL                                                    // compile with -DLOCAL to enable, silent on the judge
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", dbg_out(__VA_ARGS__)
template<class T> void dbg_out(T x) { cerr << x << '\n'; }
template<class T, class... R> void dbg_out(T x, R... r) { cerr << x << ", "; dbg_out(r...); }
#else
#define dbg(...)
#endif
// Byteland has n cities, and m roads between them. The goal is to construct new roads so that there is a route between any two cities.
// Your task is to find out the minimum number of roads required, and also determine which roads should be built.

int p[100005];
int find(int x){ while(p[x]!=x) x = p[x] = p[p[x]]; return x; }

int main() {
    cin.tie(0)->sync_with_stdio(0);    

    int n,m; cin >> n >> m; // cities and roads 
    


    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        p[find(a)] = find(b);          // no rank needed, path compression is enough here
    }
    vector<int> reps;
    for(int i=1;i<=n;i++) if(find(i)==i) reps.push_back(i);

    cout << reps.size()-1 << "\n";
    for(size_t i=1;i<reps.size();i++)
        cout << reps[i-1] << " " << reps[i] << "\n";

    




}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED