Connect cities

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

vector<int> p;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  p.resize(n + 1);
  iota(p.begin(), p.end(), 0);

  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    p[find(a)] = find(b);
  }

  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