Connect cities

#include <bits/stdc++.h> 
using namespace std;
#define REP(i,a,b) for (int i = a; i < b; i++)

int n;
vector<int> connexes;
vector<bool> visited;
vector<vector<int>> adjacence;

void dfs(int s,int index) {
        if (visited[s]) return;
        visited[s] = true;
        connexes[s] = index;
        for (auto u: adjacence[s]) {
            dfs(u,index);
        }
    }
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m;
    cin>>n>>m;
    connexes.resize(n);
    visited.assign(n, false);
    adjacence.resize(n);

    REP(i,0,m){
        int a;
        int b;
        cin>>a>>b;
        a--;b--;
        adjacence[a].push_back(b);
        adjacence[b].push_back(a);
    }
    REP(i,0,n){ 
        if (!visited[i]){
            dfs(i,i);
        }
    }
    sort(connexes.begin(),connexes.end());

    int k =0;
    queue<pair<int,int>> q; 
    REP(i,0,n-1){ 
        if (connexes[i]!=connexes[i+1]){
            q.push({connexes[i],connexes[i+1]});
            k++;
        }
    }
    cout<<k<<"\n"; 
    REP(i,0,k){ 
        cout << q.front().first+1<<" "<<q.front().second+1<<"\n";
        q.pop();
        }

    return 0; 
}

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