Connect cities

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

const int N = 1e5+1;
vector<int> A[N];
bool Z[N];
int n, m;

void dfs(int i) {
	Z[i] = 1;
	for (int j : A[i]) {
		if (!Z[j]) dfs(j);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		A[a-1].push_back(b-1);
		A[b-1].push_back(a-1);
	}
	vector<int> v;
	for (int i = 0; i < n; ++i) {
		if (!Z[i]) {
			dfs(i);
			v.push_back(i+1);
		}
	}
	cout << v.size() - 1 << '\n';
	for (int i = 1; i < (int)v.size(); ++i) {
		cout << v[i-1] << ' ' << v[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