#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("kingdom.in");
ofstream fout("kingdom.out");

int n, m, a1, a2, b1, b2;
bool conn[101][101];
int c[101][100], nc[101];
struct { int a, b, from, len; } q[1000000]; // celjsh (ja negatiivi - kvazipaaris)
int nq;
bool vis[101][101], qvis[101][101];
struct { int a, b; } p[1000000];
int np;



bool canmove(int a1, int b1, int a2, int b2, bool quasi)
{
	return (a2 != b2 && conn[a2][b2] && !((quasi && qvis[a2][b2]) || (!quasi && vis[a2][b2])) && !(a2 == b1 && b2 == a1));
}



void move(int from, int a1, int b1, int a2, int b2, bool quasi = false)
{
	if ((a1 < 0 && !(a2 == b1 && b2 == a1)) || (a1 > 0 && canmove(a1, b1, a2, b2, quasi))) {
		if (quasi) qvis[a2][b2] = true; else vis[a2][b2] = true;
		q[nq].a = (quasi ? -a2 : a2);
		q[nq].b = (quasi ? -b2 : b2);
		q[nq].len = q[from].len + 1; //(a1 == a2 || b1 == b2 ? 1 : 2);
		q[nq].from = from;
		nq++;
	}
}



int main()
{
	int i, j, k;
	int a, b;

	fin >> n >> m >> a1 >> b1 >> a2 >> b2;
	for (i = 0; i < m; i++) {
		fin >> a >> b;
		conn[a][b] = conn[b][a] = true;
		c[a][nc[a]++] = b;
		c[b][nc[b]++] = a;
	}

	q[0].a = a1;
	q[0].b = b1;
	q[0].len = 0;
	q[0].from = -1;
	nq = 1;
	vis[a1][b1] = true;
	for (i = 0; i < nq; i++)
		if (q[i].a < 0) {
			// no quasi uz iisto
			move(i, q[i].a, q[i].b, -q[i].a, -q[i].b);
		} else {
			for (j = 0; j < nc[q[i].a]; j++)
				for (k = 0; k < nc[q[i].b]; k++) {
					move(i, q[i].a, q[i].b, c[q[i].a][j], q[i].b);
					if (q[nq - 1].a == a2 && q[nq - 1].b == b2) goto southpark;
					move(i, q[i].a, q[i].b, q[i].a, c[q[i].b][k]);
					if (q[nq - 1].a == a2 && q[nq - 1].b == b2) goto southpark;
					// tagad kjeepas
					move(i, q[i].a, q[i].b, c[q[i].a][j], c[q[i].b][k], true);
					if (q[nq - 1].a == a2 && q[nq - 1].b == b2) goto southpark;
				}
		}

southpark:
	// output - bishku jaapachakaree ir
	fout << q[nq - 1].len << ' ';
	// saskaitaam dazhaados paarus
	for (i = nq - 1; i != -1; i = q[i].from) {
		if (q[i].a > 0) {
			// celjsh buus jaadrukaa no otra gala
			p[np].a = q[i].a;
			p[np].b = q[i].b;
			np++;
		}
	}
	fout << np << '\n';
	// celjsh
	for (i = np - 1; i >= 0; i--) fout << p[i].a << ' ' << p[i].b << '\n';
	
	return 0;
}