#include <stdio.h>
#include <string.h>
#include <search.h>

int numEdges,numVertices,nextVertexNumber=0;
int *tailHeader,*headTab;

struct edge {
  int tail,head;
};
typedef struct edge edgeType;
edgeType *edgeTab;
char **stringNameTable;

int name2number(char *x)
{
ENTRY e,*ep;

e.key=x;
ep=hsearch(e,FIND);
if (ep)
  return (int) ep->data;
if (nextVertexNumber==numVertices)
{
  printf("Too many vertices\n");
  exit(0);
}
e.key=(char *)malloc(strlen(x)+1);
if (!e.key)
{
  printf("error 0\n");
  exit(0);
}
strcpy(e.key,x);
stringNameTable[nextVertexNumber]=e.key;
e.data=(char*) nextVertexNumber;
ep=hsearch(e,ENTER);
if (!ep)
{
  printf("hsearch ENTER failed!\n");
  exit(0);
}
return nextVertexNumber++;
}

void readInput()
{
int i;
char tailString[21],headString[21];

scanf("%d %d",&numVertices,&numEdges);
stringNameTable=(char**) malloc(numVertices*sizeof(char*));
if (!stringNameTable)
{
  printf("error 0\n");
  exit(0);
}
tailHeader=(int*) malloc((numVertices+1)*sizeof(int));
if (!tailHeader)
{
  printf("error 1\n");
  exit(0);
}

edgeTab=(edgeType*) malloc(numEdges*sizeof(edgeType));
headTab=(int*) malloc(numEdges*sizeof(int));
if (!edgeTab || !headTab)
{
  printf("error 2\n");
  exit(0);
}

if (!hcreate(numVertices))
{
  printf("error 3\n");
  exit(0);
}

for (i=0;i<numEdges;i++)
{
  scanf("%s %s",tailString,headString);
  edgeTab[i].tail=name2number(tailString);
  edgeTab[i].head=name2number(headString);
}

if (numVertices!=nextVertexNumber)
{
  printf("missing vertices\n");
  exit(0);
}
}

int tailThenHead(const void* xin, const void* yin)
/* Used in call to qsort() for buildAdjacencies() */
{
int result;
edgeType *x,*y;

x=(edgeType*) xin;
y=(edgeType*) yin;
result=x->tail - y->tail;
if (result!=0)
  return result;
else
  return x->head - y->head;
}

void buildAdjacencies()
{
/* Builds compact adjacency structure */
int duplicates=0,i,j,k;

qsort(edgeTab,numEdges,sizeof(edgeType),tailThenHead);
j=k=0;
for (i=0;i<numVertices;i++)
{
  tailHeader[i]=k;
  while (j<numEdges && edgeTab[j].tail==i)
  {
    if (j>0 && edgeTab[j].tail==edgeTab[j-1].tail &&
      edgeTab[j].head==edgeTab[j-1].head)
    {
      duplicates++;
      j++;
      continue;
    }
    headTab[k++]=edgeTab[j++].head;
  }
}
tailHeader[numVertices]=k;
if (duplicates>0)
{
  printf("%d duplicates found & removed\n",duplicates);
  numEdges-=duplicates;
}
}

void dump()
{
int i,j;

printf(" i   stringNameTable[i]\n");
for (i=0;i<numVertices;i++)
  printf("%3d    %s\n",i,stringNameTable[i]);
printf(" i  tailHeader[i]\n");
for (i=0;i<=numVertices;i++)
  printf("%3d    %3d\n",i,tailHeader[i]);
printf(" i  headTab[i]\n");
for (i=0;i<numEdges;i++)
  printf("%3d    %3d\n",i,headTab[i]);
for (i=0;i<numVertices;i++)
{
  printf("tail vertex %s, head vertices are: ",stringNameTable[i]);
  for (j=tailHeader[i];j<tailHeader[i+1];j++)
    printf("%s ",stringNameTable[headTab[j]]);
  printf("\n");
}
}

int intCompare(const void* xin, const void* yin)
{
int *x,*y;

x=(int*) xin;
y=(int*) yin;
return (*x) - (*y);
}

int edgePresent(int tailNum,int headNum)
{
return (NULL!=(int*)bsearch(&headNum,&headTab[tailHeader[tailNum]],
  tailHeader[tailNum+1]-tailHeader[tailNum],sizeof(int),intCompare));
}

int testSymmetric()
{
int i,j;

for (i=0;i<numVertices;i++)
  for (j=tailHeader[i];j<tailHeader[i+1];j++)
    if (!edgePresent(headTab[j],i))
      return 0;
return 1;
}

void girth()
{
int *queue,*dist,*back1,*back2,i,j,k,p,tail,head;
int girthTest;
int girth,girthVertex,otherPath;

queue=(int*) malloc(numVertices*sizeof(int));
dist=(int*) malloc(numVertices*sizeof(int));
back1=(int*) malloc(numVertices*sizeof(int));
back2=(int*) malloc(numVertices*sizeof(int));
if (!queue || !dist || !back1 || !back2)
{
  printf("allocation error\n");
  exit(0);
}
girth=99999;
for (i=0;i<numVertices;i++)
{
  for (j=0;j<numVertices;j++)
    dist[j]=99999;

// INSERT CODE HERE

}

free(queue);
free(dist);
free(back2);
printf("girth is %d\n",girth);
if (girth!=99999)
{
  printf("path 1: %s ",stringNameTable[girthVertex]);
  for (i=back1[girthVertex];i!=(-1);i=back1[i])
    printf("%s ",stringNameTable[i]);
  printf("\n");
  printf("path 2: %s %s ",stringNameTable[girthVertex],
    stringNameTable[otherPath]);
  for (i=back1[otherPath];i!=(-1);i=back1[i])
    printf("%s ",stringNameTable[i]);
  printf("\n");
}
free(back1);
}

main()
{

readInput();
printf("buildAdjacencies()\n");
buildAdjacencies();
//dump();
printf("testSymmetric()\n");
if (testSymmetric())
  girth();
else
  printf("graph is not symmetric\n");
}