#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

//哈密頓回路 回溯法
/*
輸入：
5 7
1 2
1 4
2 3
2 5
3 5
3 4
4 5

輸出:
k=1  0  0 -1 -1 -1
k=2  0  1  0 -1 -1
k=3  0  1  2  0 -1
k=4  0  1  2  3  0
k=3  0  1  2  4 -1
k=4  0  1  2  4  0
k=4  0  1  2  4  3
1
*/
int path[11][11]={0};
int next[11]={-1};
int visited[11]={0};
int save;

void print(int num,int k)
{
	int i;
	cout<<"k="<<k;
	for(i=0;i<num;i++)
		printf("%3d",next[i]);
	cout<<endl;
}

void init()
{
	int i;
	for(i=0;i<11;i++)
		next[i]=-1;//next[i]表示第i次要訪問的點(diǎn)，初始化，表示還未開始訪問
}
bool HAMIDUN(int num,int start)
{
	int k=1,now=1,s=start;
	init();//初始化
	visited[start]=1;//訪問第一個(gè)點(diǎn)
	next[start]=start;
	while(k>=1)//從第2個(gè)點(diǎn)開始訪問
	{
		next[k]++;//開始訪問，訪問下一個(gè)點(diǎn)，設(shè)為A處
		print(num,k);
		while(next[k]<num)
		{
			if(visited[next[k]]==0&&path[next[k-1]][next[k]]==1) 
				break;//第k次正在訪問的點(diǎn)符合條件
			next[k]++;
		}
		if(next[k]<num)
		{	
			//該點(diǎn)符合條件
			if(k==num-1&&path[next[k]][start]==1)
			{
			//訪問到最后一個(gè)點(diǎn)，且已形成哈密頓回路
				visited[next[k]]=1;
				print(num,k);
				return true;
			}
			else if(k<num-1) 
			{	//還未訪問完，繼續(xù)下一次訪問
				visited[next[k]]=1;//訪問該點(diǎn)
				k++;
			}
		}
		else
		{	//該點(diǎn)不符合條件，回溯
			visited[next[k-1]]=0;//上一次訪問的點(diǎn)無效（也就是還未訪問）
			//注意，此時(shí)next[k-1]不是為0，而是為上次訪問后停留的位置
			//回溯后從上次停留的位置后面（注意A處）開始訪問
			next[k]=-1;	//本次訪問未得到合適的點(diǎn)	
			k--;
		}
	}
	return false;
}

int main()
{
	int num,ta,tb,pathnum,i;
	scanf("%d%d",&num,&pathnum);
	for(i=0;i<pathnum;i++)
	{
		scanf("%d%d",&ta,&tb);
		path[ta-1][tb-1]=path[tb-1][ta-1]=1;
	}
	printf("%d",HAMIDUN(num,0));
	return 0;
}















#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

//哈密頓回路 回溯法
/*
輸入：
5 7
1 2
1 4
2 3
2 5
3 5
3 4
4 5

輸出:
k=1  0  0 -1 -1 -1
k=2  0  1  0 -1 -1
k=3  0  1  2  0 -1
k=4  0  1  2  3  0
k=3  0  1  2  4 -1
k=4  0  1  2  4  0
k=4  0  1  2  4  3
1
*/
int path[11][11]={0};
int next[11]={-1};
int visited[11]={0};
int save;

void print(int num,int k)
{
	int i;
	cout<<"k="<<k;
	for(i=0;i<num;i++)
		printf("%3d",next[i]);
	cout<<endl;
//	system("pause");
}

void init()
{
	int i;
	for(i=0;i<11;i++)
		next[i]=-1;
}
bool HAMIDUN(int num,int start)
{
	int k=1,now=1,s=start;
	init();
	visited[start]=1;
	next[start]=start;
//	next[0]=1;
	while(k>=1)
	{
		next[k]++;
		print(num,k);
//		save=next[k];
//		visited[next[k]]=0;
		while(next[k]<num)
		{
			if(visited[next[k]]==0&&path[next[k-1]][next[k]]==1) 
			{
				s=next[k];
				break;
			}
			next[k]++;
		}
		if(k==num-1&&path[next[k]][start]==1&&next[k]<num)
		{
			visited[next[k]]=1;
			print(num,k);
//			next[k]=start;
			return true;
		}
		else if(next[k]<num&&k<num-1) 
		{
			visited[next[k]]=1;
			k++;
		}
		else
		{
//			visited[next[k-1]]=0;
//			next[k-1]=0;
//			if(k<num) 
//			{
		
//			if(next[k]>=num) next[k]=save;
//			if(next[k]>=num) visited[save]=0;
//			else 
			visited[next[k-1]]=0;
//			next[k-1]++;
				next[k]=-1;		
//			}
	//		next[k]=0;
	//		visited[next[k]]=0;
			k--;
		}
	}
	return false;
}

int main()
{
	int num,ta,tb,pathnum,i;
	scanf("%d%d",&num,&pathnum);
	for(i=0;i<pathnum;i++)
	{
		scanf("%d%d",&ta,&tb);
		path[ta-1][tb-1]=path[tb-1][ta-1]=1;
	}
	printf("%d",HAMIDUN(num,0));
	return 0;
}