//* Problem  : K.
//* Contest  : NEERC-2003
//* Type     : Solution
//* Date     : 2008.08.01
//* Author   : alt
//* Language : C++
//* Compiler : Microsoft Visual C++ 6.0

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

typedef pair <int,int> PIII;
typedef vector <int> VI;
typedef vector <vector<int> > VVI;
typedef vector <pair<int,int> > VPII;
typedef vector <vector<pair<int,int> > > VVPII;

#define int64 long long
#define PI (2.0 * acos(0.0))
#define MP make_pair
#define PB push_back
#define SZ(a) (int)a.size()
#define FOR(i, n) for (int i = 0; i < (int)n; i++)
#define FORSZ(i, a) FOR(i, SZ(a))
#define FORE(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define FORR(i, a, b) for (int i = (int)(a); i >= int(b); i--)
#define INF 1000000000
#define INFL 1000000000000000000LL
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()

inline int si(){int tt; scanf("%d", &tt); return tt;}

int n, m, a1, b1, a2, b2;

VVI a;

int r[1024][2], res_k, res_count;

VVPII q;
VVPII prev;

int dp[128][128];

int adj[128][128];

int K[128][128];
int prA[128][128];
int prB[128][128];
int type[128][128];

int rr[128];

char ok[128][128][6000];

void save(int x, int y, int d)
{
	r[d][0] = x;
	r[d][1] = y;
	if (type[x][y] == 2)
	{
		d--;
		r[d][0] = x;
		r[d][1] = y;
	}
	if (!rr[x]){rr[x] = 1; res_count++;}
	if (!rr[y]){rr[y] = 1; res_count++;}
	if (d)
		save(prA[x][y], prB[x][y], d-1);
}

void solve()
{
	q.assign(4*m + 1, VPII());
	prev.assign(4*m + 1, VPII());
	q[0].PB(MP(a1, b1));
	prev[0].PB(MP(a1, b1));
	for (int k = 0; k < SZ(q); k++)
		FORSZ(i, q[k])
		{
			int k1 = q[k][i].first;
			int k2 = q[k][i].second;
			int k1p = prev[k][i].first;
			int k2p = prev[k][i].second;
			if (K[k1][k2]) continue;
			K[k1][k2] = k;
			prA[k1][k2] = k1p;
			prB[k1][k2] = k2p;
			if (k1 == k1p || k2 == k2p)
				type[k1][k2] = 1;
			else
				type[k1][k2] = 2;

			FORSZ(j, a[k1])
			{
				int v = a[k1][j];
				if (v != k2 && adj[v][k2] && !K[v][k2] && !ok[v][k2][k+1] && !ok[v][k2][k])
				{
					ok[v][k2][k+2] = 1;
					ok[v][k2][k+1] = 1;
					ok[v][k2][k] = 1;
					q[k+1].PB(MP(v, k2));
					prev[k+1].PB(MP(k1, k2));
#ifdef _DEBUG
					printf("To [%d %d] from [%d %d]\n", v, k2, k1, k2);
#endif
				}
			}
			FORSZ(j, a[k2])
			{
				int v = a[k2][j];
				if (v != k1 && adj[k1][v] && !K[k1][v] && !ok[k1][v][k+1] && !ok[k1][v][k])
				{
					ok[v][k2][k] = 1;
					ok[v][k2][k+1] = 1;
					ok[v][k2][k+2] = 1;
					q[k+1].PB(MP(k1, v));
					prev[k+1].PB(MP(k1, k2));
#ifdef _DEBUG
					printf("To [%d %d] from [%d %d]\n", k1, v, k1, k2);
#endif
				}
			}
			FORSZ(j1, a[k1]) FORSZ(j2, a[k2])
			{
				int v1 = a[k1][j1];
				int v2 = a[k2][j2];
				if (adj[v1][v2] && !K[v1][v2] && !(v1 == k2 && v2 == k1)  && !ok[k1+1][v1][v2]  && !ok[k1+2][v1][v2])
				{
					ok[v1][v2][k+2] = 1;
					q[k+2].PB(MP(v1, v2));
					prev[k+2].PB(MP(k1, k2));
#ifdef _DEBUG
					printf("To [%d %d] from [%d %d]\n", v1, v2, k1, k2);
#endif
				}
			}
		}
	res_k = K[a2][b2];
	save(a2, b2, res_k - 1);
}

void result()
{
	printf("%d %d\n", res_k, res_count);
	FOR(i, res_k)
		if (!i || r[i][0] != r[i-1][0] || r[i][1] != r[i-1][1])
		printf("%d %d\n", r[i][0], r[i][1]);
}

int main()
{
#ifdef _DEBUG
	freopen("1064", "r", stdin);
#endif
	n = si();
	m = si();
	a1 = si();
	b1 = si();
	a2 = si();
	b2 = si();
	a.assign(n + 1, VI());
	FOR(i, m)
	{
		int v1 = si(), v2 = si();
		a[v1].PB(v2);
		a[v2].PB(v1);
		adj[v1][v2] = adj[v2][v1] = 1;
	}
	solve();
	result();
	return 0;
}

