#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#define MAX_GRUPPE 100

typedef struct {
    int mems[101]; /* max 100 inimest */
    int num_mem;
} grupp_t;

grupp_t *grupid;
unsigned int gruppe = 0;

typedef struct {
    int p[2];
} seosed_t;

int inimesi, seoseid;
int *seosed_olemas;

void kustuta_grupp(int gr2) {
    int i;
    
    if(gr2 >= gruppe)
        return;
    for(i=gr2;i<gruppe-1;i++) {
        grupid[i] = grupid[i+1];
    }
    gruppe--;
}

void liida_grupid(int gr1, int gr2) {
    int x;
    int kokku;
    int indeks;
    
    if(gr1 > gruppe || gr2 > gruppe)
        return;
        
    kokku = grupid[gr1].num_mem + grupid[gr2].num_mem /* -1 */;
    for(x=grupid[gr1].num_mem;x<kokku;x++) {
        indeks = x - grupid[gr1].num_mem;
        grupid[gr1].mems[x] = grupid[gr2].mems[indeks];
    }
    grupid[gr1].num_mem += grupid[gr2].num_mem;
    kustuta_grupp(gr2);
}

typedef struct {
  int arv;
  int groups[MAX_GRUPPE];
} grupi_jada_t;

/* tagastab kõikide gruppide arvud, kus liige on */
grupi_jada_t otsi_teisest(int pergr, int per) {
/* pergr - mis grupis isik on */
  grupi_jada_t jada;
  int numpergrps = 0;
  int i, j;
  int num_mem;

  jada.arv = 0;
  for(i=0;i<gruppe;i++) {
    if(i == pergr) { /* enda gruppi ei vaata */
        continue;
    }    
    num_mem = grupid[i].num_mem;
    for(j=0;j<num_mem;j++) {
      if(grupid[i].mems[j] == per) {
        jada.groups[jada.arv++] = i; /* isik on grupis i */
        continue;
      }
    }
  }
  return jada;
}

void lisa_liige(int gr, int per) {
    if(gr > gruppe) {
        return;
    }
/*    grupid[gr].mems = (int *)realloc(grupid[gr].mems, sizeof(int)*grupid[gr].num_mem);*/
    grupid[gr].mems[grupid[gr].num_mem] = per;
/*    grupid[gr].ms[grupid[gr].num_mem] = -1;*/
    grupid[gr].num_mem++;
}

void lisa_grupp(int p1, int p2) { /* isik1, isik2*/
    int i, j;
    int num_mem;

    for(i=0;i<gruppe;i++) {
        num_mem = grupid[i].num_mem;
        for(j=0;j<num_mem;j++) {
            if(grupid[i].mems[j] == p1) {
              lisa_liige(i, p2);
              return;
            } else if(grupid[i].mems[j] == p2) {
              lisa_liige(i, p1);
              return;
            }
        }
    }
    /* liikmed ei olnud üheski grupis - uus grupp */
    gruppe++;
    grupid = (grupp_t *)realloc(grupid, sizeof(grupp_t) * gruppe);
    grupid[gruppe-1].num_mem = 0;
    lisa_liige(gruppe-1, p1);
    lisa_liige(gruppe-1, p2);
}

void tee_yksik_grupp(int p) {
    gruppe++;
    grupid = (grupp_t *)realloc(grupid, sizeof(grupp_t) * gruppe);
    grupid[gruppe-1].num_mem = 0;
    lisa_liige(gruppe-1, p);
}

void seos_olemas(int p) {
    if(!seosed_olemas) {
        seosed_olemas = (int *) calloc(inimesi+1, sizeof(int));
    }
    seosed_olemas[p] = 1;
}

void create_dummy_persons() {
    int i;
    if(!seosed_olemas) {
        for(i=1;i<inimesi+1;i++)
                tee_yksik_grupp(i);
    } else {
        for(i=1;i<inimesi+1;i++) {
                if(!seosed_olemas[i])
                                tee_yksik_grupp(i);
        }
    }
}

void print_groups() {
    int i, j;
    for(i=0;i<gruppe;i++) {
        printf("grupp %d: ", i);
        for(j=0;j<grupid[i].num_mem;j++) {
                printf("%d ", grupid[i].mems[j]);
        }
        printf("\n");
    }
}

int main() {
    seosed_t *s_jada;
    int i, j;
    FILE *f;
    
    f = fopen("sug.sis", "r");
    if(!f) {
        FILE *fout;
        fout = fopen("sug.val", "w");
        fprintf(fout, "sug.sis ei leitud");
        fclose(fout);
        return 0;
    }
    
    fscanf(f, "%d %d", &inimesi, &seoseid);
    if(seoseid)
        s_jada = (seosed_t *)malloc(sizeof(seosed_t) * seoseid);
    
    for(i=0;i<seoseid;i++) {
        fscanf(f, "%d %d", &(s_jada[i].p[0]), &(s_jada[i].p[1]));
        seos_olemas(s_jada[i].p[0]);
        seos_olemas(s_jada[i].p[1]);        
        lisa_grupp(s_jada[i].p[0], s_jada[i].p[1]);
    }
    fclose(f);
    create_dummy_persons();

    /* liidame grupid, mis on seotud */
    int mem, teine_grupp;
    int x;
    grupi_jada_t isiku_grupid;
    for(i=0;i<gruppe;i++) {
      for(j=0;j<grupid[i].num_mem;j++) {
          /* vaatame, kas on teise grupi liige */
          mem = grupid[i].mems[j];
          isiku_grupid = otsi_teisest(i, mem);
          /* liidame grupid kokku */
          for(x=0;x<isiku_grupid.arv;x++)
            liida_grupid(i, isiku_grupid.groups[x]);
      }
    }

    /* leiame mitteseotud inimesed, esimene isik igast grupist */
    f = fopen("sug.val", "w");
    if(gruppe == 1) { /* üks grupp, omavahel seotud */
       fprintf(f, "0");
    } else {
        fprintf(f, "%d\n", gruppe);
          for(i=0;i<gruppe;i++)
            fprintf(f, "%d ", grupid[i].mems[0]);
    }
    fclose(f);
}