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

struct Tedge{int i,j;};

Tedge beg,fin;

#define MAXN 100
#define MAXM 2000
#define INF 2000000000
int n,m;

bool edge[MAXN][MAXN];

Tedge prev[MAXN][MAXN];

unsigned int dist[MAXN][MAXN];

Tedge Queue[MAXM + 5];
int s,f;

void wave()
{
	memset(dist,-1,sizeof(dist));
	dist[beg.i][beg.j] = 0;
	s = 0;
	f = 1;
	Queue[0] = beg;
	while ((s != f) && (dist[fin.i][fin.j] >= INF))
	{
		Tedge from = Queue[s];
		int fromi = from.i;
		int fromj = from.j;
		Tedge to;
		int toi,toj;
		int j;
		unsigned int newDist = dist[fromi][fromj] + 1;
		for (j = 0; j < n; j++)
		{
			toi = -1;
			if (edge[fromj][j] && (j != fromi))
			{
				toi = fromj;
				toj = j;
			}
			if ((toi != -1) && (dist[toi][toj] > newDist))
			{
				dist[toi][toj] = newDist;
				to.i = toi;
				to.j = toj;
				Queue[f++] = to;
				prev[toi][toj] = from;
			}
		}
		for (j = 0; j < n; j++)
		{
			toi = -1;
			if (edge[fromi][j] && edge[fromj][j])
			{
				toi = fromi;
				toj = j;
			}
			if ((toi != -1) && (dist[toi][toj] > newDist))
			{
				dist[toi][toj] = newDist;
				to.i = toi;
				to.j = toj;
				Queue[f++] = to;
				prev[toi][toj] = from;
			}
		}
		
		s++;
	}
}

bool was[MAXN];

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;
	}
}

Tedge Path[MAXM];

void outp()
{
	memset(was,0,sizeof(was));
	Tedge cur = fin;
	Tedge next;
	int len = 0;
	was[fin.i] = true;
	was[fin.j] = true;
	while ((cur.i != beg.i) || (cur.j != beg.j))
	{
		Path[len++] = cur;
		next = prev[cur.i][cur.j];
		cur = next;
		was[cur.i] = true;
		was[cur.j] = true;
	}
	int i;
	int cnt = 0;
	for (i = 0; i < n; i++)
		if (was[i])
			cnt++;
	printf("%d %d\n",len + 1, cnt);
	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();
	wave();
	outp();
	return 0;
}
