/* Problem 8--Acceptable Strings
   This was a straightforward emulation of a finite state automaton.
   There was nothing particularly tricky about this one. */
#include <stdio.h>
#include <stdlib.h>

typedef struct ST { /* state info:  where do I go on 0 and 1, and is
                       it a final state? */
 int on0, on1, f;
} ST;

int main (int argc, char **argv);
void Process (FILE *out, ST *states, int N, int *cs);
void ProcessCase (FILE *out, ST *states, int N);
int next (char *bstr);

int main (int argc, char **argv) {

  int r, N, S, F, i, f, cs;
  FILE *in, *out;
  ST *states;

 in = fopen ("prob8.in","r");
 out = fopen ("prob8.out","w");
 cs = 0;
 for (;;) {
  fscanf (in,"%d %d %d",&N,&S,&F);
 if (N+S+F==0) break;
  states = malloc (S*sizeof (ST));
  i = 0;  /* Read in states, and scale:  the problem has them start */
  for (;;) { /* at 1; we will start them at 0. */
  if (i==S) break;
   fscanf (in,"%d %d",&states[i].on0,&states[i].on1);
   states[i].on0--;
   states[i].on1--;
   states[i].f = 0;
   i++;
  }
  i = 0; /* Read in the final states. */
  for (;;) {
  if (i==F) break;
   fscanf (in,"%d",&f);
   states[f-1].f = 1;
   i++;
  }
  Process (out,states,N,&cs);
  free (states);
 }
 fclose (in);
 fclose (out);
 r = EXIT_SUCCESS;
 return r;
}

/* Process computes the number strings the machine accepts and prints
   the results to out.  states is the list of states, N is the maximum
   string length and cs is the case number. */
void Process (FILE *out, ST *states, int N, int *cs) {

  int i;

 fprintf (out,"Case %d:\n",++*cs);
 i = 0;
 for (;;) {
 if (i > N) break; /* Process them one at a time. */
  ProcessCase (out,states,i);
  i++;
 }
}

/* ProcessCase prints to out the number of strings of length N
   accepted by the machine represented by states. */
void ProcessCase (FILE *out, ST *states, int N) {

  char bstr[11];
  int i, ct, st;

 i = 0; /* Initialize string to all 0's. */
 for (;;) {
 if (i==N) break;
  bstr[i] = '0';
  i++;
 }
 bstr[N] = 0;
 ct = 0;
 for (;;) {
  i = st = 0;
  for (;;) { /* go through the machine for this string */
  if (i==N) break;
   if (bstr[i]=='0') {
    st = states[st].on0;
   } else {
    st = states[st].on1;
   }
   i++;
  }
  ct += states[st].f; /* Was it accepted? */
 if (next (bstr)) break; /* Get the next string to try. */
 }
 if (ct==1) {
  fprintf (out,"    Length = %d, 1 string accepted.\n",N);
 } else {
  fprintf (out,"    Length = %d, %d strings accepted.\n",N,ct);
 }
}

/* next updates bstr to contain the next bit string to try.  It returns
   true if there are no more to try, false otherwise. */
int next (char *bstr) {

  int done, i;

 i = 0;
 for (;;) {
 if (bstr[i] == '0' || bstr[i] == 0) break;
  bstr[i] = '0';
  i++;
 }
 if (bstr[i] == '0') { /* If the string is not all 1's, we have more */
  bstr[i] = '1';       /* to try. */
  done = 0;
 } else {
  done = 1;
 }
 return done;
}