#include<stdio.h>
#define m 30


int x[m];
void next_vertext(int [m][m],int,int);
void ham(int[m][m],int,int);


int main()
{
int n,i,j,e,v1,v2,G[m][m];
printf("\n Enter no of vertices in the graph");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
G[i][j]=0;
x[i]=0;
}
}
printf("\nEnter total edges ");
scanf("%d",&e);
for(i=1;i<=e;i++)
{
printf("\nEnter the edge");
scanf("%d%d",&v1,&v2);

G[v1][v2]=1;
G[v2][v1]=1;
}
x[1]=1;
printf("\nHamiltonian cycle\n");
ham(G,n,2);
return 0;
}


void next_vertext(int G[m][m],int n,int k)
{
int j;
while(1)
{
x[k]=(x[k]+1)%(n+1);
if(x[k]==0)
return ;
if(G[x[k-1]][x[k]]!=0)
{
for(j=1;j<k;j++)
{
if(x[j]==x[k])
break;
}
if(j==k)
{
if((k<n)||((k==n)&&G[x[n]][x[1]]!=0))

return ;
}
}
}
}

void ham(int G[m][m],int n,int k)
{
int i;
while(k!=0)
{
next_vertext(G,n,k);
if(x[k]!=0)
{
if(k==n)
{
printf("\n");
for(i=1;i<=n;i++)
printf("%d\t",x[i]);
printf("%d",x[1]);
}
else
k++;
}
else
k--;
}
}
/*
OUTPUT:-


Enter no of vertices in the graph5

Enter total edges 7

Enter the edge1 3

Enter the edge1 4

Enter the edge1 5

Enter the edge 3 4

Enter the edge3 2

Enter the edge2 5

Enter the edge2 4

Hamiltonian cycle

1 3 4 2 5 1
1 4 3 2 5 1
1 5 2 3 4 1
1 5 2 4 3 1


 Enter no of vertices in the graph5

Enter total edges 6

Enter the edge1 2

Enter the edge2 3

Enter the edge3 4

Enter the edge4 2

Enter the edge2 5

Enter the edge5 1

No Hamiltonian cycle
*/