#include <fstream.h>
#include <math.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include <queue>

using std::priority_queue;

struct point{
	long a,b,v;
};

bool operator < (const point & a, const point & b){
	return a.v < b.v;
}

bool operator == (const point & a, const point & b){
	return a.v == b.v;
}

typedef priority_queue<point> pq;
const long MAX = 111;
long dist[MAX][MAX];
long prev[MAX][MAX][2];
long mat[MAX][MAX], vertex[MAX], edge[22 * MAX][2], N, M, E, A1, B1, A2, B2;

pq Q;
void add(long a, long b, long v, long pa, long pb){
	if (dist[a][b] <= v)
		return;
	dist[a][b] = v;
	prev[a][b][0] = pa;
	prev[a][b][1] = pb;
	point p;
	p.a = a;
	p.b = b;
	p.v = v;
	Q.push(p);
}

void get(long& a, long&b, long& v){
	point res = Q.top();
	Q.pop();
	a = res.a;
	b = res.b;
	v = res.v;
}
int fcmp (const void * v1, const void * v2){
	long * l1 = (long*) v1;
	long * l2 = (long*) v2;
	if (l1[0] < l2[0])
		return -1;
	if (l1[0] < l2[0])
		return 1;
	return 0;
}

void Input(){
	cin >> N >> M >> A1 >> B1 >> A2 >> B2;
	A1--; B1--;A2--;B2--;
	E = 0;
	memset(mat, 0, sizeof mat);
	memset(vertex, -1, sizeof vertex);
	memset(edge, -1, sizeof edge);
	long a, b;
	for (long i = 0; i < M; i++){
		cin >> a >> b;
		a--;
		b--;
		mat[a][b] = mat[b][a] = 1;
		edge[E][0] = a;
		edge[E][1] = b;
		E++;
		edge[E][0] = b;
		edge[E][1] = a;
		E++;
	}
	qsort(edge, E, sizeof edge[0], fcmp);
	for (long k = 0; k < E; k++)
		if (!k || edge[k][0] != edge[k - 1][0])
			vertex[edge[k][0]] = k;
}

void Solve(){
	memset(dist, 60, sizeof dist);
	add(A1, B1, 0, -1, -1);
	long a, b, v;
	while (!Q.empty()){
		get(a, b, v);
		for (long i = 0; i < N; i++)
			if (mat[a][i] && mat[b][i]){
				add(a, i, v + 1, a, b);
				add(i, b, v + 1, a, b);
			}
		for (long e1 = vertex[a]; e1 >= 0 && edge[e1][0] == a; e1++)
			for (long e2 = vertex[b]; e2 >= 0 && edge[e2][0] == b; e2++)
				if (mat[edge[e1][1]][edge[e2][1]]){
					if (edge[e1][1] == edge[e2][0] && edge[e1][0] == edge[e2][1])
						continue;
					add(edge[e1][1], edge[e2][1], v + 2, a, b);
				}
	}		
}			
long res[10 * MAX * MAX][2];
void Output(){
	long R = 0;
	cout << dist[A2][B2];
	while (A2 != -1){
		res[R][0] = A2;
		res[R][1] = B2;
		long t = A2;
		A2 = prev[A2][B2][0];
		B2 = prev[t][B2][1];
		R++;
	}
	cout << ' ' << R << endl;
	for (long i = R - 1; i >= 0; i--){
		cout << res[i][0] + 1 << ' ' << res[i][1] + 1 << endl;
	}
}

int main(){
	ifstream fi("kingdom.in");
	ofstream fo("kingdom.out");
	cin = fi;
	cout = fo;
	Input();
	Solve();
	Output();
	return 0;
}
