#include <stdio.h>
#include <stdlib.h>
#define DEBUG 0
#define PRINT 0
#define NMAX 100
int new_hamilton_path(int n, int G[NMAX][NMAX]);
int new_hamilton_cycle(int n, int G[NMAX][NMAX]);
int hamilton_path(int n, int G[NMAX][NMAX]);
int hamilton_cycle(int n, int G[NMAX][NMAX]);
int hamuv(int n, int G[NMAX][NMAX], int nv, int u, int v, int mask[]);

/* 
   These first two routines are of type int and return
   0 if there is no Hamilton path/cycle and
   1 if there is a Hamilton path/cycle 
*/

int hamilton_path(int n, int G[NMAX][NMAX])
{
    int i, j;
    int mask[NMAX];

#if PRINT
     printf("--- Hamilton Path : ");
     fflush(stdout);
#endif
#if DEBUG
     printf("\n");
#endif

    if (n <= 1) return(1);

    for (i=0; i <n; i++)
        mask[i]=1;


    for (i=0; i <n; i++)
 
    {
        for (j=i+1; j <n; j++)
        {
#if DEBUG
            printf("From %2d to %2d\n", i, j);
            fflush(stdout);
#endif
            if (hamuv(n, G, n, i, j, mask))
            {
#if PRINT 
                printf("\n");
#endif
                return(1);
            }
        }
    }
#if PRINT 
    printf("None found. \n");
#endif
    return(0);
}
int hamilton_cycle(int n, int G[NMAX][NMAX])
{
    int i, j;
    int mask[NMAX];

#if PRINT
     printf("--- Hamilton Cycle: ");
     fflush(stdout);
#endif
#if DEBUG
     printf("\n");
#endif

    if (n <= 2) return(0);

    for (i=0; i <n; i++)
        mask[i]=1;

    for (i=0; i <n; i++)
    {
        for (j=i+1; j <n; j++)
        {
            if (G[i][j])
            {
#if DEBUG
               printf("From %2d to %2d\n", i, j);
               fflush(stdout);
#endif
               if (hamuv(n, G, n, i, j, mask))
               {
#if PRINT
                   printf("(%2d, %2d)\n", i, j);
                   fflush(stdout);
#endif
                   return(1);
               }
            }
        }
    }
#if PRINT 
    printf("None found. \n");
#endif
    return(0);
}
/* NOTE: This hamuv code is "inside the black box"
and so you may not call it! If you call this function
in your solution, you will not get any marks. */

int hamuv(int n, int G[NMAX][NMAX], int nv, int u, int v, int mask[])
/* Look for a Hamilton Path from u to v. */
{
   int i;

   if (nv ==2)
   {
#if PRINT
      if (G[u][v]) printf("(%2d, %2d) ", v, u);
      fflush(stdout);
#endif
#if DEBUG
      printf("\n");
#endif
      return(G[u][v]);
   }

   mask[u]=0;

   for (i=0; i <n; i++)
   {
       if (mask[i] && G[u][i] && i!= v)
       {
#if DEBUG
           printf("Level %2d:  Trying edge (%2d, %2d)\n", nv, u, i);
           fflush(stdout);
#endif
           if (hamuv(n, G, nv-1, i, v, mask))
           {
               mask[u]=1;
#if PRINT
               printf("(%2d, %2d) ", i, u);
               fflush(stdout);
#endif
#if DEBUG
               printf("\n");
#endif
               return(1);
           }
       }
    }
    mask[u]=1;
    return(0);
}