Shared code

#include<iostream>
#include<vector>
#include<unordered_set>
//#define REP(i,n) for(int i=0;i<n;++i)
#define REP(i,s,n) for(int i=s;i<n;++i)

using namespace std;

// merges roots only
void merge(vector<int>& U, int a, int b) {
	U[b] = a;
}

int find(vector<int>& U, int a) {
	while (a != U[a])
		a = U[a];
	return a;
}

// find + two pass path compression
int find2(vector<int>& U, int a) {
	int root = a;
	while (root != U[root])
		root = U[root];

	int next = U[a];
	while (next != root) {
		U[a] = root;
		a = next;
		next = U[a];
	}
	return root;
}

int main() {
	int n, m;
	cin >> n >> m;

	vector<int> U(n + 1);
	REP(i, 1, n + 1) U[i] = i;

	int cc_count = n;

	for (int i = 0;i < m;++i) {
		int a, b;
		cin >> a >> b;

		int root_a = find2(U, a);
		int root_b = find2(U, b);
		if (root_a != root_b) {
			merge(U, root_a, root_b);
			cc_count--;
		}
	}
	cout << cc_count - 1 << endl;
	if (cc_count > 1) {

		unordered_set<int> roots;
		roots.reserve(cc_count);

		int root_1 = find2(U, 1);
		roots.insert(root_1);

		for (int i = 2;i < n + 1 && (int)roots.size() < cc_count;++i) {
			int root_i = find2(U, i);
			if (!roots.contains(root_i)) {
				roots.insert(root_i);
				cout << root_1 << ' ' << root_i << endl;
			}
		}
	}
}