#include	<stdio.h>
#include	<memory.h>

struct Tedge{int i,j;};

Tedge beg,fin;
int begE, finE;

#define MAXN 202
#define MAXM 5002
#define INF 2000000000
int n,m;

bool edge[MAXN][MAXN];

Tedge prev[MAXN][MAXN];

unsigned int dist[MAXN][MAXN];

Tedge edges[MAXN];

bool done[MAXN][MAXN];

void Dijkstra()
{
	memset(done,0,sizeof(done));
	memset(dist,-1,sizeof(dist));

	dist[beg.i][beg.j] = 0;
	Tedge minEdge;
	
	int it = 0;
	int m2 = 2 * m;
	while (!done[fin.i][fin.j] && (it < m2 + 5))
	{
		it++;
		int i,j;
		unsigned int minDist = INF;

		for (i = 0; i < m2; i++)
		{
			if ((!done[edges[i].i][edges[i].j]) && (dist[edges[i].i][edges[i].j] < minDist))
			{
				minEdge = edges[i];
				minDist = dist[edges[i].i][edges[i].j];
			}
		}

		if (minDist >= INF)
			return;


		Tedge from = minEdge;
		int fromi = from.i;
		int fromj = from.j;
		int toi,toj;

		for (i = 0; i < m2; i++)
		{
			toi = edges[i].i;
			toj = edges[i].j;
			if (!done[toi][toj] && ((toi != fromj) || (toj != fromi)))
			{
				int cst;
				if ((edge[fromi][toi]) && edge[fromj][toj])
					cst = 2;
				else if ((fromi == toi) && edge[fromj][toj])
					cst = 1;
				else if ((fromj == toj) && edge[fromi][toi])
					cst = 1;
				else
					cst = -1;
				if (cst != -1)
				{
					if (dist[fromi][fromj] + cst < dist[toi][toj])
					{
						dist[toi][toj] = dist[fromi][fromj] + cst;
						prev[toi][toj] = from;
					}
				
				}
			}
		}
		done[minEdge.i][minEdge.j] = true;
	}
}

void inp()
{
	int i;
	int a,b;
	memset(edge,0,sizeof(edge));
	for (i = 0; i < m; i++)
	{
		scanf("%d %d",&a,&b);
		a--;
		b--;
		edge[a][b] = true;
		edge[b][a] = true;
		edges[2 * i].i = a;
		edges[2 * i].j = b;
		edges[2 * i + 1].i = b;
		edges[2 * i + 1].j = a;
	}
	for (i = 0; i < 2*m; i++)
	{
		if ((edges[i].i == beg.i) && (edges[i].j == beg.j))
			begE = i;
		if ((edges[i].i == fin.i) && (edges[i].j == fin.j))
			finE = i;
	}
}

Tedge Path[MAXM];

void outp()
{
	Tedge cur = fin;
	Tedge next;
	int len = 0;
	while ((cur.i != beg.i) || (cur.j != beg.j))
	{
		Path[len++] = cur;
		next = prev[cur.i][cur.j];
		cur = next;
	}
	int i;
	printf("%d %d\n",dist[fin.i][fin.j],len + 1);
	printf("%d %d\n",beg.i + 1, beg.j + 1);
	while (len)
	{
		--len;
		printf("%d %d\n",Path[len].i + 1, Path[len].j + 1);
	}
}

int main()
{
	freopen("kingdom.in","r",stdin);
	freopen("kingdom.out","w",stdout);
	scanf("%d %d",&n,&m);
	scanf("%d %d",&beg.i,&beg.j);
	scanf("%d %d",&fin.i,&fin.j);
	beg.i--;
	beg.j--;
	fin.i--;
	fin.j--;
	inp();
	Dijkstra();
	outp();
	return 0;
}
