Shared code

#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;
 }
}