Connect cities

#include <bits/stdc++.h>

using namespace std;

//Definitions for quicker writing
#define REP(i,a,b) for (int i = a; i < b; i++)

//Typedefs for quicker writing
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;


void dfs(int s, bool visited[], vi roads[]){
	if(visited[s]) return;
	visited[s] = true;
	for (auto u: roads[s]){
		dfs(u, visited, roads);
	}
}


int main() {
	//IO optimization
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	//Input definition
	int n,m;

	cin >> n >> m;

	vi roads[n];
	
	for(int i = 0; i < m; i++) {
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		roads[a].push_back(b); 
		roads[b].push_back(a);
	}	 	


	//Main part
		
	REP(i,0,n){
		sort(roads[i].begin(), roads[i].end());
	}

	bool visited[n] = {false};

	dfs(0, visited, roads);

	ostringstream buffer;

	int nroads = 0;

	REP(i,0,n){
		if(!visited[i]){
			nroads++;
			buffer << 1 << " " << i+1 << "\n";	
			dfs(i, visited, roads);
		}
	}

	//Write out
	cout << nroads << "\n";	
	cout << buffer.str();

	//Return
	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