/*                                                */
/*  ppf.c            Last update: 7 December 2015 */
/*                                                */
/*  Plantri Projective Filter                     */
/*                                                */
/*  A filter for  `plantri'  program to select    */
/*  graphs which admit an orientation-reversing   */
/*  involution without fixed vertices and fixed   */
/*  edges (thus, giving a graph on RP^2).         */
/*  Nonsimple input graphs are skipped.           */
/*                                                */
/*  Author:  S.Yu.Orevkov                         */
/*           orevkov(at)math.ups-tlse.fr          */
/*                                                */
/*  compilation:                                  */
/*        gcc ppf.c -o ppf                        */
/*                                                */
/*  usage:                                        */
/*        plantri [....] | ppf [-u] [-b]          */
/*                                                */
/*        -u  do not output the graphs            */
/*            (only the number of them)           */
/*        -b  select bipartite graphs on RP^2     */
/*                                                */
/*  The output is almost the same as plantri's    */
/*  ascii output. The selected graphs are output  */
/*  as they would be output by `plantri -a' but:  */
/*                                                */
/*  1) The names of vertices are changed from     */
/*     (a,b,c,...) to (a,b,c,...; A,B,C,...) so   */
/*     that the involution maps a->A, b->B, etc.  */
/*  2) We list the neighbourhoods of lowercase    */
/*     vertices only                              */
/*                                                */
/*================================================*/
/* Version Dec-07-2015:                           */
/*  All nonsimple input graphs are skipped        */
/*  (before, some of them were skipped randomly)  */
/*                                                */
/* Version Jul-27-2013:                           */
/*  This version was used for the computations in */
/*  [Ann Fac Sci Toulouse, vol.24(2015), 205-226] */

#include <stdlib.h>
#include <stdio.h>
#include <strings.h>

#define YES    1
#define NO     0
#define UNDEF -1
#define FAIL   0
#define OK     1
#define s_max  4096

typedef unsigned char byte;

int  count=0;     /* counter for graphs on RP2  */
int  countbip=0;  /* counter for bipartite ones */
int  nv=0;        /* the number of vertices     */
byte s[s_max];    /* heap for neighbours        */
int   *deg;  /* deg[v] = degree of a vertex v              */
byte **nbhd; /* nbhd[v][i], i=1,...,deg[v] neighbours ov v */
int   *img;  /* img[v] = image of v under the involution   */
int   *ie;   /* ie[v] = the initial edge at v              */
int   *fd;   /* fd[v] = the fund.domain containing v       */
int   *nn;   /* nn[v] = the new name of v (for the output) */
int   *oldnm;/* oldnm[u] = v iff  nn[v] = u  and fd[v] = 0 */
int   *par;  /* par[v] = the parity of  dist(v0,v)         */
int   maxdeg;
int   distr[256]; /* distr[d] = # vertices of degree d     */
int   last_nn;

int map_nbhd( int v );
void clear_mem(void){
  free(nbhd);free(deg);free(img);free(ie);free(fd);free(nn);
  free(oldnm);free(par);
}
void ini_mem(int nv){
  nbhd = (byte **)malloc( nv*sizeof(byte *) );
#define mem_nv  (int *)malloc( sizeof(int)*nv )
  deg=mem_nv; img=mem_nv; ie=mem_nv;
  fd=mem_nv;  nn=mem_nv; oldnm=mem_nv; par=mem_nv;
}
void bad_input(void){ puts("bad input"); exit(9); }

void show( void ){int v;
  for( v=0; v<nv; v++ ){ printf(" %d->%d",v,img[v]);}
  printf("\n ie:");
  for( v=0; v<nv; v++ ){ printf(" %d ",ie[v]);}
  putchar('\n');
}

int optU = NO, optB = NO, bip, simple;

int main( int argc, char *argv[] ){ byte *p; int v,i,c,d,eof=NO;
  for( i=0; i<argc; i++ )printf("%s ",argv[i]);
  putchar('\n');

  fread(s,1,15,stdin);
  if(strncmp(s,">>planar_code<<",15))bad_input();
  if(argc > 1){ if( strncmp(argv[1],"-u",2) == 0 )optU = YES; }
  if(argc > 1){ if( strncmp(argv[1],"-b",2) == 0 )optB = YES; }
  if(argc > 1){ if( strncmp(argv[1],"-ub",3) == 0 )optU = optB = YES; }
  if(argc > 1){ if( strncmp(argv[1],"-bu",3) == 0 )optU = optB = YES; }
  if(argc > 2){ if( strncmp(argv[2],"-u",2) == 0 )optU = YES; }
  if(argc > 2){ if( strncmp(argv[2],"-b",2) == 0 )optB = YES; }
  if(argc > 2){ if( strncmp(argv[2],"-ub",3) == 0 )optU = optB = YES; }
  if(argc > 2){ if( strncmp(argv[2],"-bu",3) == 0 )optU = optB = YES; }

  while(YES){int mindd,d0,v0,n0,v1,n,i1,found=NO;
    /** each iteration of this loop corresponds to a graph **/
    simple = bip = YES;  /* bip = bipartite */

    if( (n=getchar()) != nv ){ if(n<=0){ eof=YES; break; } 
      if(nv>0)clear_mem();
      nv=n; ini_mem(n);
      printf("nv = %d\n",nv);
    }

    for( v=0; v<nv; v++ )deg[v]=0;
    maxdeg=0;
    for( p=s,v=0; v<nv; v++ ){ nbhd[v]=p;  /*read the graph*/
      for( i=0; i<nv; i++ )nn[i]=0;   /* added Dec 7, 2015 */
      nn[v]=1;                        /* added Dec 7, 2015 */
      while( (c=getchar())!=0 ){
        if( c==EOF ){ if(v>0||p>s)bad_input();else break; }
        *p++ = c-1; deg[v]++;
        if( (nn[c-1]++)>0 )simple=NO; /* added Dec 7, 2015 */
      }
      if( deg[v] > maxdeg )maxdeg=deg[v];
    }
    if(eof)break;
    if( !simple )continue;            /* added Dec 7, 2015 */

    for( d=0; d<=maxdeg; d++ )distr[d]=0;
    for( v=0; v<nv; v++ ) distr[ deg[v] ]++;
    
    /* primary parity test: for any d, the number of  */
    /* vertices of degree d should be even            */

    for( mindd=10000,d0=0,d=0; d<=maxdeg; d++ ){ 
        if(distr[d]&1){ break; }
        if(distr[d]<2)continue;
        if( (i=d*(distr[d]-1)) < mindd ){mindd = i; d0=d;}
    }
    if( d<=maxdeg )continue;

    /* choose v0 - the seed of the involution */
    for( v0=0; v0<nv; v0++ )if( deg[v0]==d0 )break;

    for( v1=v0+1; v1<nv && (!found); v1++ ){if(deg[v1]!=d0)continue;
      for( i1=0; i1<d0 && (!found); i1++ ){
        /** try to map v0->v1, nbhd[v0][0] -> nbhd[v1][i1] **/

        for( v=0; v<nv; v++ )ie[v]=img[v]=fd[v]=par[v]=UNDEF;
        img[v0]=v1;  img[v1]=v0; ie[v0]=0; ie[v1]=i1;
        fd[v0]=0;    fd[v1]=1;   nn[v0] = nn[v1] = last_nn = 0;
        oldnm[0]=v0;             par[v0]=par[v1]=0;

        /** (img[v] != UNDEF && ie[v] == UNDEF) means that the **/
        /** images of all neighbours of v are already assigned **/

        while( YES ){

           for( v=0; v<nv; v++ ){
              if( img[v] != UNDEF && ie[v] != UNDEF )break;
           }
           if ( v==nv ) { found = YES; break; }
           if ( map_nbhd(v) == FAIL ) break;
        }
      }
    }

    if( found ){
      count++; if(bip)countbip++;
      if( !optU ){ int j,u;

         printf("%d ",nv/2);

         for( j=0; 2*j<nv; j++ ){ v = oldnm[j];
            for( i=0; i<deg[v]; i++ ){ u = nbhd[v][i];
               putchar( (byte)nn[u] + (fd[u]?'A':'a') );
            }
            putchar(2*j==nv-2 ? ' ' : ',');
         }
         printf(" bip=%d; ",bip);
         for( d=2; d<=maxdeg; d++ )printf(" %d",distr[d]/2);
         putchar('\n');
      }
    }

  }  /** go to the next graph **/

  printf(" %d  graphs on RP2 are found; %d  are bipartite\n",
            count, countbip );
  exit(0);
}

/*  Assuming that the image of v0 is defined, we try  */
/*    to define the images of the neighbours of v0    */

int map_nbhd( int v0 ){
    int dv,du,v1,i0,i1,i,j,u0,u1,p0,p1; byte *nv0,*nv1,*nu0,*nu1;

    v1 = img[v0];   dv = deg[v0];
    i0 = ie[v0];    i1 = ie[v1];
    nv0 = nbhd[v0]; nv1 = nbhd[v1];
    p0 = par[v0];   p1 = par[v1];

    for( j=0; j<dv; j++ ) if( nv0[j] == v1 ) return FAIL;

    for( j=0; j<dv; j++,i0++,i1-- ){ if(i0==dv)i0=0; if(i1<0)i1=dv-1;
      u0=nv0[i0]; u1=nv1[i1]; du = deg[u0];

      if( u0==u1 || du!=deg[u1] )return FAIL;
      if( img[u0] != UNDEF ){
        if( img[u0]!=u1 || img[u1]!=u0 )return FAIL;
        if( par[u0]==par[v0] ){ bip = NO; if( optB )return FAIL; }
      }
      else{
        if( img[u1] != UNDEF )return FAIL;
        par[u0] = 1 - par[v0]; par[u1] = 1 - par[v1];
      }
    }

    i0 = ie[v0]; i1 = ie[v1];
    for( j=0; j<dv; j++,i0++,i1-- ){ if(i0==dv)i0=0; if(i1<0)i1=dv-1;
      nu0 = nbhd[u0=nv0[i0]]; nu1 = nbhd[u1=nv1[i1]]; du = deg[u0];
      if( img[u0]==UNDEF ){
          nn[u0] = nn[u1] = ++last_nn; oldnm[ last_nn ] = u0;
          img[u0] = u1; img[u1] = u0;  fd[u0] = 0; fd[u1] = 1;
          for( i=0; i<du; i++ ){
              if( nu0[i]==v0 ) ie[u0]=i;
              if( nu1[i]==v1 ) ie[u1]=i;
          }
      }
    }
    ie[v0] = ie[v1] = UNDEF;
    return OK;
}