/*
TASK:obez
LANG:C
*/
#include <stdio.h>

#define N 100

int  m, w[N], br=1, a[N][N], v[N], min=100, tek[N], pos[N]={0};

void init()
{
     int i, j;
	     for (i=0;i<m;i++)
	    for (j=0;j<m;j++)
		a[i][j]=11000;
}
void func()
{
	int i, j, k ,q;

	for (k=0;k<m;k++)
	    for (i=0;i<m;i++)
		for (j=0;j<m;j++)
		    {
			if (a[k][j]>a[k][i]+a[i][j])
				{
				 br=0;
				 a[k][j]=a[k][i]+a[i][j];
				}
		    }

	for (i=0;i<m;i++) a[i][i]=11000;
}

void mw(int p,int x, int y)
{
	int i, j;

	pos[x]=1;

	for (i=0;i<m;i++)
		{
			tek[p]=x+1;
			if (x==y)
			{
			   if (p<min)
			   {
			       min=p;
			       for (j=0;tek[j];j++) v[j]=tek[j];

			   }
			}
			else if (a[x][i]&&!pos[i]) {mw(p+1,i,y);}
			tek[p]=0;
		}
	pos[x]=0;
}

int main()
{
	int i, j, t, p;
	long k;
	int min1[3]={0};
	min1[0]=11000;
		scanf ("%d %ld",&m,&k);
		init();
		for (i=0;i<k;i++)
		{
			scanf ("%d %d",&t,&p);
			a[t-1][p-1]=1;
		}

	func();
	t=a[0][m-1];

	if (t==(m-1))
	{
		for (i=0;i<m;i++) if (a[0][i]==(t-1))
				  {
				     for (j=0;j<m;j++)
				     {
				      if ((a[i][j]+a[j][i])<min1[0])
				      {
				      min1[0]=a[i][j]+a[j][i];
				      min1[1]=i;
				      min1[2]=j;
				      }
				     }
				  }
	       br=0;
	       min=11000;
	       mw(0,0,min1[1]);
	       for (i=0;v[i];i++)
	       {
		   if (v[i]==v[i+1]||v[i]==w[br+i-1]) i++;
		   w[br+i]=v[i];
	       }
	       br=br+i;
	       min=11000;
	       mw(0,min1[1],min1[2]);
	       for (i=1;v[i];i++)
	       {
		   if (v[i]==v[i+1]||v[i]==w[br+i-1]) i++;
		   w[br+i-1]=v[i];
	       }
	       i--;
	       br=br+i;
	       min=11000;
	       mw(0,min1[2],min1[1]);
	       for (i=1;v[i];i++)
	       {
		   if (v[i]==v[i+1]||v[i]==w[br+i-1]) i++;
		   w[br+i-1]=v[i];
	       }
	       i--;
	       br=br+i;
	       min=11000;
	       mw(0,min1[1],m-1);
	       for (i=1;v[i];i++)
	       {
		   if (v[i]==v[i+1]||v[i]==w[br+i-1]) i++;
		   w[br+i-1]=v[i];
	       }
	       i--;
	       br=br+i;
	}
	if (t!=(m-1))
	{
		  min1[0]=11000;
		  for (i=1;i<m;i++)
		  if (a[0][i]+a[i][m-1]>t && a[0][i]+a[i][m-1]>min1[0])
		  {
		   min1[0]=a[i][0]+a[i][m-1];
		   min1[1]=i;
		  }
		  br=0;
		  min=11000;
		  mw(0,0,min1[i]);
		       for (i=1;v[i];i++)
		       {
		   if (v[i]==v[i+1]||v[i]==w[br+i-1]) i++;
			   w[br+i]=v[i];
		       }
		       i--;
		       br=br+i;
		  min=11000;
		  mw(0,min1[i],m-1);
		       for (i=1;v[i];i++)
		       {
		   if (v[i]==v[i+1]||v[i]==w[br+i-1]) i++;
			   w[br+i]=v[i];
		       }
		       i--;
		       br=br+i;
	}

	br=0;
	for (i=0;i<5*m;i++) {if (w[i]) br++;}
	br--;
	printf ("%d\n",br);
	for (i=0;i<5*m;i++) if (w[i]) printf ("%d ",w[i]);
	return 0;

}
