Connect cities

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; ++i)
#define BR "\n"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> pi;
typedef unordered_set<int> usi;

void dfs(vi adj[], usi& not_visited, int s, vi& comp) {
  if (not_visited.count(s) == 0) return;
  not_visited.erase(s);
  comp.push_back(s);
  // process s
  for (auto u : adj[s]) {
    dfs(adj, not_visited, u, comp);
  }
}

int main() {
  // freopen("cities.txt", "r", stdin);
  int n, m;
  cin >> n >> m;

  vi adj[n + 1];
  unordered_set<int> not_visited;

  REP(i, 0, m) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
    not_visited.insert(a);
    not_visited.insert(b);
  }

  // determine connected components

  vector<vi> comp;
  int ci = 0;

  while (not_visited.size() > 0) {
    comp.push_back(vi());
    dfs(adj, not_visited, *not_visited.begin(), comp[ci]);
    ci++;
  }

  // connect disjoint connected components
  cout << ci - 1 << BR;
  REP(i, 0, ci - 1) { cout << comp[i][0] << " " << comp[i + 1][0] << BR; }

  return EXIT_SUCCESS;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

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