#include <stdio.h>
#include <string.h>

FILE *f;

#define INF 15000

typedef struct _list {
	int b;
	struct _list* next;
} list;


list* adj[100];
int hody[100][100];
int pary[100][100];
int nexta[100][100];
int nextb[100][100];

bool mas[100][100];

void add(list* &l, int b)
{
	list* tmp;
	tmp = new list;
	tmp->b = b;
	tmp->next = l;
	l = tmp;
}

int func(int a, int b)
{
	if (hody[a][b] != INF)
		return hody[a][b];
	list *i; list *j;

	hody[a][b] = INF-1;

	long _hody = INF-1;
	long _pary = 0;
	int _nexta, _nextb;
	int cur;


	// a ostajotsja na meste
	for (i=adj[b]; i != NULL; i=i->next)
	{
		if ((i->b != a)&&(mas[a][i->b]))
		{
			cur = func(a, i->b) + 1;
			if (cur < _hody)
			{
				_hody = cur;
				_pary = pary[a][i->b] + 1;
				_nexta = a;
				_nextb = i->b;
			}
		}
	}

	// b ostajotsja na meste
	for (i=adj[a]; i != NULL; i=i->next)
	{
		if ((i->b != b) && (mas[i->b][b]))
		{
			cur = func(i->b, b) + 1;
			if (cur < _hody)
			{
				_hody = cur;
				_pary = pary[i->b][b] + 1;
				_nexta = i->b;
				_nextb = b;
			}
		}
	}

	
	
	// a i b izmenjajustja
	for (i=adj[a]; i!=NULL; i=i->next)
	{
		if (a == i->b) continue;
		for (j=adj[b]; j!=NULL; j=j->next)
		{
			if (b == j->b) continue;

			if ((a == j->b) && (b == i->b))
				continue; // nelzja odnovrem. po odnomu portalu

			if (mas[i->b][j->b])
			{
				cur = func(i->b, j->b) + 2;
				if (cur < _hody)
				{
					_hody = cur;
					_pary = pary[i->b][j->b] + 1;
					_nexta = i->b;
					_nextb = j->b;
				}
			}
		}
	}

	
	if (_hody >= INF)
		_hody = INF-1;

	hody[a][b] = _hody;
	pary[a][b] = _pary;
	nexta[a][b] = _nexta;
	nextb[a][b] = _nextb;

	return _hody;
}

int main()
{
	int n,m,a1,b1,a2,b2;
	int i,j,a,b;

	memset(adj, 0, sizeof(adj)); // NULLs
	memset(mas, 0, sizeof(mas)); // false

	
	f = fopen("kingdom.in","rt");
	fscanf(f, "%d %d %d %d %d %d", &n, &m, &a1, &b1, &a2, &b2);
	a1--; b1--; a2--; b2--;
	for (i=0;i<m;i++)
	{
		fscanf(f, "%d %d", &a, &b);
		a--; b--;
		add(adj[a], b);
		add(adj[b], a);
		mas[a][b] = mas[b][a] = true;
	}

	for (i=0;i<n;i++) for (j=0; j<n;j++) hody[i][j] = INF;

	hody[a2][b2] = 0;
	pary[a2][b2] = 0;
	fclose(f);

	if ((a1 == a2) && (b1 == b2))
	{
		f = fopen("kingdom.out","wt");
		fprintf(f,"0 1\n%d %d\n", a2, b2);
		fclose(f);
	}
	else
	{
		int c = func(a1,b1);
	
		f = fopen("kingdom.out","wt");

		fprintf(f, "%d %d\n", c, 1+pary[a1][b1]);
		fprintf(f, "%d %d\n", a1+1, b1+1);

		int ii, jj, k;

		i = a1; j = b1;

		for (k=0; k<pary[a1][b1]; k++)
		{
			ii = nexta[i][j];
			jj = nextb[i][j];
			fprintf(f, "%d %d\n", ii+1, jj+1);
			i = ii;
			j = jj;
		}

//		fprintf(f, "%d %d\n", a2+1, b2+1);

		fclose(f);
	}

	return 0;
}