#include <stdio.h>
#define MAXN 110
#define MAX 2100
#define INF 1000000000

struct st
	{
	int x,y;
	st(int _x=0,int _y=0):x(_x),y(_y){}
	};

int n,m;
int dist[MAX][MAX];
st mas[MAX];
int kolm=0;
int G[MAX][MAX];
int d[MAX];
int par[MAX],used[MAX];
st ans[MAX];
int kolans;

int Find(st now)
	{
	int i;
	for (i=0;i<kolm;i++)
		if (now.x==mas[i].x && now.y==mas[i].y) return i;
	return -1;
	}

int Solve(st p1, st p2)
	{
	if (p1.x==p2.x)
		{
		if (G[p1.y][p2.y]) return 1;
		return INF;
		}

	if (p1.y==p2.y)
		{
		if (G[p1.x][p2.x]) return 1;
		return INF;
		}
	
	if (G[p1.x][p2.x]==1 && G[p1.y][p2.y]==1 && (p1.x!=p2.y || p1.y!=p2.x)) return 2;
	return INF;
	}

void Dijkstra(int beg,int end)
	{
	int i,j;
	for (i=0;i<kolm;i++)
		{
		d[i]=INF;
		par[i]=-1;
		used[i]=0;
		}
	d[beg]=0;
	for (i=0;i<kolm;i++)
		{
		int tecmin=-1;
		for (j=0;j<kolm;j++)
			if (!used[j])
				if (tecmin==-1 || d[tecmin]>d[j]) tecmin=j;
		if (tecmin==-1 || d[tecmin]==INF || tecmin==end) return;
		used[tecmin]=1;
		for (j=0;j<kolm;j++)
			if (!used[j])
				if (d[j]>d[tecmin]+dist[tecmin][j])
					{
					par[j]=tecmin;
					d[j]=d[tecmin]+dist[tecmin][j];
					}
		}
	}

int main()
	{
	freopen("kingdom.in","rt",stdin);
	freopen("kingdom.out","wt",stdout);

	scanf("%d %d", &n, &m);
	int i,j;
	int b1,b2,e1,e2,p1,p2;
	scanf("%d %d %d %d", &b1, &b2, &e1, &e2);
	b1--, b2--, e1--, e2--;
		
	for (i=0;i<m;i++)
		{
		scanf("%d %d", &p1, &p2);
		p1--,p2--;
		G[p1][p2]=G[p2][p1]=1;
		if (Find( st(p1, p2) )==-1)
			{
			mas[kolm].x=p1;
			mas[kolm++].y=p2;
			}
		if (Find( st(p2, p1) )==-1)
			{
			mas[kolm].x=p2;
			mas[kolm++].y=p1;
			}		
		}

	for (i=0;i<kolm;i++)
		for (j=0;j<kolm;j++)
			if (i!=j) dist[i][j]=INF;
			else dist[i][j]=0;

	for (i=0;i<kolm;i++)
		for (j=i+1;j<kolm;j++)
			{
			int res=Solve(mas[i], mas[j]);
			dist[i][j]=dist[j][i]=res;
			}

	int i1=Find(st(b1, b2));
	int i2=Find(st(e1, e2));

	Dijkstra( i1, i2 );
	printf("%d", d[i2]);

	while (i2!=i1)
		{
		int r1=par[i2];
		ans[kolans++]=mas[i2];
		i2=r1;
		}
	
	ans[kolans++]=mas[i1];
	printf(" %d\n", kolans);
	for (i=kolans-1;i>=0;i--)
		printf("%d %d\n", ans[i].x+1, ans[i].y+1);

	return 0;
	}