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