#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cassert>
    #include<string>
    #include<cmath>
    #include<iostream>
    #include<cmath>
    #include<sstream>
    #include<stdio.h>
    #include<stdlib.h>
     using namespace std;

  int const N = 20;
  int const M = 40;
  int const W = 99;

  //  N vertices and M edges

  int parent[N];
  int banda[N];
  int degree[N];
  int numberchosen = 0;

  struct edge
   {
    int s;
    int t;
    int w;
    bool chosen = false;
   };

  void initvertices()
   {
    for(int i = 0; i < N; i++)
     {
      parent[i] = i;
      banda[i] = 1;
      degree[i] = 0;
     }
   }

  edge edges[M];

  void swapedges(edge&e1,edge&e2)
   {
    edge temp = e1;
    e1 = e2;
    e2 = temp;
   }

void sortedges()
   {
    for(int i = 0; i < M-1 ; i++)
     for(int j = i+1; j < M; j++)
      if(edges[j].w < edges[i].w) swapedges(edges[i],edges[j]);
   }

  void initedges()
   {
    for(int k = 0; k < M; k++)
     {
      edges[k].s = rand() % N;
      edges[k].t = rand() % (N-1);
      if (edges[k].t == edges[k].s) edges[k].t++;
      edges[k].w = 1+rand() % W-1; 
      degree[edges[k].s]++;
      degree[edges[k].t]++;
     }
   }

  void displayedges()
   {
    for(int k = 0; k < M; k++)
     {
      cout << k << ": (" << edges[k].s<< "," << edges[k].t << ") "
           << edges[k].w;
      if(edges[k].chosen) cout << " chosen";
      cout << endl;
     }
   }

  void displayvertices()
   {
    for(int i = 0; i < N; i++)
     {
      cout << i << " " << degree[i];
      cout << " " << parent[i] << " " << banda[i] << endl;
     }

   }

  int find(int i)
   {
    if (parent[i] == i) return i;
    else
     {
      int rslt = find(parent[i]);
      parent[i] = rslt; // path compression
      return rslt;
     }
   }

  void unia(int i, int j)
   {
    parent[i] = j;
    banda[j] = banda[i]+banda[j];
    banda[i] = 0;
   }

  void processedge(int k)
   {
    int i = find(edges[k].s);
    int j = find(edges[k].t);
    if(i != j)
     {
      edges[k].chosen = true;
      numberchosen++;
      if(banda[i] < banda[j]) unia(i,j);
      else if(banda[j] < banda[i]) unia(j,i);
      else if(i < j) unia(i,j);
      else if(j < i) unia(j,i);
     }
   }

  int main()
   {
    srand(0);
    initvertices();
    initedges();
    sortedges();
    displayedges();
    displayvertices();
    return 1;
   }