// gcc -O3 -o strongly3 strongly3.c
#include<pthread.h>
#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdarg.h>
#include<math.h>
#include<string.h>

struct node { struct node *t[3]; int nb;};
typedef struct node node;

node *r;
int i, j, k, l, t, lim, mot[100000], b, len[100000], **tmp, tt, c = 0, on = 1;
char ch[3000], **mat;
FILE *in;

node *new_node(){
 node *p = (node*)malloc(sizeof(node));
 p->t[0] = p->t[1] = p->t[2] = 0;
 p->nb = -1;
 return p;
}

int ch_cr(int *m){
 node *p = r; int x;
 for(x = 0; x < l-1; x++) if(!(p = p->t[m[x]])){ printf("error!!\n"); exit(0); }
 return p->nb;
}
  
void add_cr(int *m){
 node *p = r; int x;
 for(x = 0; x < l-1; x++){
  if(!(p->t[m[x]])) p->t[m[x]] = new_node();
  p = p->t[m[x]];
 }
 if(p->nb < 0) p->nb = c++;
}

void usage(){
 printf("Usage: strongly3 input_file\n");
 exit(0);
}

int main(int ac, char **av){
 if(ac < 2) usage();
 in = fopen(av[1], "r");
 tmp = (int**)malloc(30000*sizeof(int*));
 for(fgets(ch, 2000, in), k = 0, l = strlen(ch)-1; strcmp(ch, "\n"); fgets(ch, 2000, in), k++){
  tmp[k] = (int*)malloc(l*sizeof(int));
  for(j = 0; j < l; j++) tmp[k][j] = ch[j]-'0';
 }
 fclose(in);
 r = new_node();
 for(i = 0; i < k; i++) add_cr(tmp[i]);
 printf("Rauzy graph with %d vertices of length %d and %d arcs of length %d\n", k, l-1, c, l);
 mat = (char**)malloc(c*sizeof(char*));
 for(i = 0; i < c; i++) mat[i] = (char*)malloc(c*sizeof(char));
 for(i = 0; i < c; i++) for(j = 0; j < c; j++) mat[i][j] = 0;
 for(i = 0; i < k; i++) mat[ch_cr(tmp[i])][ch_cr(tmp[i]+1)] = 1;
 while(on) for(i = on = 0; i < c; i++) for(b = 0; b < c; b++) if(mat[i][b]) for(j = 0; j < c; j++) if(mat[b][j] && !mat[i][j]) mat[i][j] = on = 1;
 for(i = 0; i < c; i++) on += mat[i][i];
 if(on == c) printf("The Rauzy graph is strongly connected\n"); else printf("The Rauzy graph is NOT strongly connected\n");
}