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);

    while(true){
        auto k = lower_bound(visited, visited+n, 0) - visited;
        nbr++;
        edges.push_back({s, k});

        if(k != n) {
            
            dfs(k);
            s = k;
        } else {
            break;
        }
    }

    cout << nbr << endl;
    for(auto e : edges) {
        cout << e.first+1 << " " << e.second+1 << endl;
    }
    

}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER