CSES - Shared codeLink to this code: https://cses.fi/paste/8718d4c0654b5be9662ea2/
#include<bits/stdc++.h>
using namespace std;
class DSU{
vector<int>parent,weight;
int paths;
public:
DSU(int n){
parent.resize(n);
weight.resize(n,1);
paths=0;
for(int i=0;i<n;i++) parent[i]=i;
}
int find(int vertex){
if(vertex==parent[vertex]){
return vertex;
}
return parent[vertex]=find(parent[vertex]);
}
bool Union(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
if(weight[a]>weight[b])swap(a,b);
parent[a]=b;
weight[b]+=weight[a];
paths=max(paths,weight[b]);
return true;
}
int getRoads(){
return paths;
}
};
int main(){
int n,m,cityA,cityB;
cin>>n>>m;
DSU sol(n+1);
for(int i=0;i<m;i++){
cin>>cityA>>cityB;
sol.Union(cityA,cityB);
}
set<int>nodes;
for(int i=1;i<=n;i++){
nodes.insert(sol.find(i));
}
vector<int>num(nodes.begin(),nodes.end());
cout<<nodes.size()-1<<endl;
for(int i=0;i<num.size()-1;i++){
cout<<num[i]<<" "<<num[i+1]<<endl;
}
}