Connect cities

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

typedef long long ll;

const ll N = 100000;

vector<ll> adj[N];

ll visited[N] = {0};

void dfs(ll s) {
    if (visited[s] == -1) return;
    visited[s] = -1;

    for (auto u: adj[s]) {
        dfs(u);
    }
}

int main() {
    ll n;
    cin >> n;
    ll m;
    cin >> m;    

    ll nbr = 0;
    ll s = 0;

    vector<pair<ll,ll>> edges;
    ll a,b;

    for(ll i = 0; i<m; i++) {
        cin >> a;
        cin >> b;
        adj[a-1].push_back(b-1);
        adj[b-1].push_back(a-1);
    }

    
    dfs(0);
    for(ll i = 1; i<n; i++){
        if(visited[i] == -1) continue;
        else {
            dfs(i);
            nbr++;
            edges.push_back({s, i});
            s = i;
        }
        
    }

    cout << nbr << "\n";
    for(auto e : edges) {
        cout << e.first+1 << " " << e.second+1 << "\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