#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
typedef vector<int> vint;
typedef queue<int> qint;
const int N = 110;
const int M = 1100;
const int K = 1100000;
int nVert, nEdge;
int n,m,uf,vf,ul,vl;
vint adj1[N], adj[K];
int rev[K][2];
int num[N][N], inc[N][N];
int dist[K], prev[K];
int tdist[K];
int main()
{
	FILE *inf = fopen("kingdom.in","rt");
	FILE *outf = fopen("kingdom.out","wt");
	int register i,j,k;
	int u,v, usize, vsize, start, end;
	int nv, pv, u1, v1, last;
	fscanf(inf,"%ld%ld",&n,&m);
	fscanf(inf,"%ld%ld",&uf,&vf);
	fscanf(inf,"%ld%ld",&ul,&vl);
	--ul;--vl;
	--uf;--vf;
	for(i=0;i<n;i++)
	{
		adj1[i].resize(0);
	}
	for(i=0;i<m;i++)
	{
		int a,b;
		fscanf(inf,"%ld%ld",&a,&b);
		--a;
		--b;
		adj1[a].push_back(b);
		adj1[b].push_back(a);
		inc[a][b] = 1;
		inc[b][a] = 1;
	}
	for(i=0;i<n;i++)
	{
		inc[i][i] = 0;
	}
	nVert = 0;
	for(i=0;i<n;i++)
	{
		int last  = adj1[i].size();
		for(j=0;j<last;j++)
		{
			int tmp = nVert++;
			rev[tmp][0] = i;
			rev[tmp][1] = adj1[i][j];
			num[i][adj1[i][j]] = tmp;
		}
	}
	int nVert0 = nVert;
	for(i=0;i<nVert0;i++)
	{
		adj[i].resize(0);
	}
	for(i=0;i<nVert;i++)
	{
		u = rev[i][0];
		v = rev[i][1];
		usize = adj1[u].size();
		vsize = adj1[v].size();
		for(j=0;j<vsize;j++)
		{
			v1 = adj1[v][j];
			if(inc[u][v1])
			{
				adj[i].push_back(num[u][v1]);
				//adj[num[u][v1]].push_back(i);
			}
		}
		for(j=0;j<usize;j++)
		{
			u1 = adj1[u][j];
			if(inc[u1][v])
			{
				adj[i].push_back(num[u1][v]);
				//adj[num[u1][v]].push_back(i);
			}
		}
		for(j=0;j<usize;j++)
		{
			u1 = adj1[u][j];
			for(k=0;k<vsize;k++)
			{
				v1 = adj1[v][k];
				if(inc[u1][v1] 
					&& (u1 != v || v1 != u))
				{
					nv = num[u1][v1];
					adj[i].push_back(-nv);
					//adj[nv].push_back(tmp);
					//adj[tmp].push_back(i);
				}
			}
		}
	}
	for(i=0;i<2*nVert;i++)
	{
		dist[i] = -1;
		prev[i] = -1;
	}
	qint q1;
	start = num[ul][vl];
	dist[start] = 0;
	tdist[start] = 1;
	q1.push(start);
	end = num[uf][vf];
	while(!q1.empty() && prev[end] == -1)
	{
		pv = q1.front();
		q1.pop();
		if(pv >= nVert)
		{
			nv = pv - nVert;
			if(dist[nv] >= 0)
				continue;
			dist[nv] = dist[pv] + 1;
			tdist[nv] = tdist[pv] + 1;
			prev[nv] = pv;
			q1.push(nv);
		}else
		{
			last = adj[pv].size();
			for(j=0;j<last;j++)
			{
				nv = adj[pv][j];
				if(nv > 0)
				{
					if(dist[nv] >= 0)
						continue;
					dist[nv] = dist[pv] + 1;
					tdist[nv] = tdist[pv] + 1;
					prev[nv] = pv;
				}else
				{
					nv = nVert - nv;
					if(dist[nv] >= 0)
						continue;
					dist[nv] = dist[pv] + 1;
					tdist[nv] = tdist[pv];
					prev[nv] = pv;
				}
				q1.push(nv);
			}
		}
	}
	fprintf(outf,"%ld %ld\n",dist[end],tdist[end]);
	while(end != start)
	{
		if(end < nVert)
		{
			fprintf(outf,"%ld %ld\n",rev[end][0]+1, rev[end][1]+1);
		}
		end = prev[end];
		if(end == -1)
			break;
	}
	fprintf(outf,"%ld %ld\n",ul+1, vl+1);
	fclose(inf);
	fclose(outf);
	return 0;
}
