Connect cities

#include<iostream> 
#include<vector>
using namespace std;

vector<int>carrateres;
vector<vector<int>>adj;
vector<bool>visited;

void dfs (int s) {
  visited[s] = true;
  for (auto u : adj[s]) {
    if (not visited[u]) {
      dfs(u);
    }
  }
}

int main() {
    int n, m;
    cin >> n >> m;
    adj = vector<vector<int>> (n+1);
    visited = vector<bool> (n+1);
    for (int i = 0 ; i < m; i++) {
      int a, b;
      cin >> a >> b;
      adj[a].push_back(b);
      adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
      if (not visited[i]) {
        carrateres.push_back(i);
        dfs(i);
      }
    }
    int k = carrateres.size() - 1;
    cout << k << endl;
    for (int i = 0; i < k; i++) {
      cout << carrateres[i] << " " << carrateres[i + 1] << endl;
    }
    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