#include <algorithm>
#include <set>
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <string.h>

using namespace std;


FILE* in=fopen("kingdom.in","r");
//FILE* in=stdin;
FILE* out=fopen("kingdom.out","w");
//FILE* out=stdout;

struct point
{
	long x,y;
} reb[5000],rez[5000],pred[105][105],k;
long ms[105][105],flag[105][105],kolx[105][105];

set<point> st;

bool operator<(const point &a,const point &b)
{
	if (kolx[a.x][a.y]!=kolx[b.x][b.y]) 
		return kolx[a.x][a.y]<kolx[b.x][b.y];
	if (a.x!=b.x)
		return a.x<b.x;
	return a.y<b.y;
}

void move(long x,long y,long prx,long pry,long kx)
{
	if (flag[x][y]) return;
	if (ms[x][y]==0) return;
	flag[x][y]=1;
	pred[x][y].x=prx;
	pred[x][y].y=pry;
	kolx[x][y]=kx;
	
	point a;
	
	a.x=x;
	a.y=y;

	st.insert(a);
}
long nerav(long a,long b)
{
	if (a!=b) return 1;
	return 0;
}
int main()
{
	long i,j,stx,sty,enx,eny,a,b,kr,n,m,x,y;
	fscanf(in,"%ld%ld",&n,&m);
	fscanf(in,"%ld%ld",&stx,&sty);
	stx--;sty--;
	fscanf(in,"%ld%ld",&enx,&eny);
	enx--;eny--;

	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if (i==j) ms[i][j]=1; else ms[i][j]=0;
	
	kr=0;
	for(i=0;i<m;i++)
	{
		fscanf(in,"%ld%ld",&a,&b);
		a--;b--;
		ms[a][b]=ms[b][a]=1;
		reb[kr].x=a;
		reb[kr++].y=b;
		reb[kr].x=b;
		reb[kr++].y=a;
	}
	
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			flag[i][j]=0;

	st.clear();

	move(stx,sty,-1,-1,0);
	while(!st.empty())
	{
		k=*st.begin();
		st.erase(k);
		x=k.x;
		y=k.y;
		x=x;
		for(i=0;i<kr;i++)
			if (ms[x][reb[i].x] && ms[y][reb[i].y] && (reb[i].y!=x || reb[i].x!=y))
				move(reb[i].x,reb[i].y,x,y,kolx[x][y]+nerav(x,reb[i].x)+nerav(y,reb[i].y));
	}
	long dl=0,kx=kolx[enx][eny];
	rez[dl].x=enx;
	rez[dl++].y=eny;
	while(pred[enx][eny].x!=-1)
	{
		x=pred[enx][eny].x;
		y=pred[enx][eny].y;
		
		enx=x;
		eny=y;

		rez[dl].x=enx;
		rez[dl++].y=eny;
	}
	fprintf(out,"%ld %ld\n",kx,dl);
	for(i=dl-1;i>=0;i--)
		fprintf(out,"%ld %ld\n",rez[i].x+1,rez[i].y+1);
	return 0;
}