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

#include <algorithm>
using namespace std;

int n,m;

bool a[100][100];

int to[100][100];
int nto[200];

int si,sj,di,dj;

int d[3][100][100];
int pi[3][100][100];
int pj[3][100][100];
int pk[3][100][100];

int qi[40001];
int qj[40001];
int qk[40001];
int b,e;
int A,B,C;
void push(int i, int j, int k, int cost, int A, int B, int C)
{
    if(d[k][i][j]) return;
    pi[k][i][j]=A;
    pj[k][i][j]=B;
    pk[k][i][j]=C;
    qi[e]=i;
    qj[e]=j;
    qk[e]=k;
    d[k][i][j]=cost;
    e++;
    if(e==40001) e=0;
}

bool pop(int& i, int& j, int &k, int& cost)
{
    if(b==e) return false;
    i=qi[b];
    j=qj[b];
    k=qk[b];
    b++;
    if(b==40001) b=0;
    cost=d[k][i][j];
    return true;
}
int wi[40001];
int wj[40001];
int wk[40001];
int t;
int main()
{
  freopen("kingdom.in","r",stdin);
  freopen("kingdom.out","w",stdout);

  int i,j,k;
  scanf("%d%d",&n,&m);
  scanf("%d%d%d%d",&si,&sj,&di,&dj);
  si--;sj--;
  di--;dj--;
  memset(d,0,sizeof(d));
  memset(nto,0,sizeof(nto));
  memset(a,0,sizeof(a));

  while(m--)
  {
  	scanf("%d%d",&i,&j);
  	i--;
  	j--;
	if(!a[i][j])
	{
  		a[i][j]=true;
  		a[j][i]=true;
  		to[i][nto[i]++]=j;
  		to[j][nto[j]++]=i;
	}
  }
       
  b=e=0;

  push(si,sj,0,1,0,0,0);
  int cost;
  int h,g;

  while(pop(A,B,C,cost)&&!d[0][di][dj])
  {
        if(C==0)
        {
             for(j=0;j<nto[A];j++)
             {
                 g=to[A][j];
                 if(a[g][B])
                 {
                     push(g,B,0,cost+1,A,B,C);
                 }
                 else
                     push(g,B,2,cost+1,A,B,C);
             }
             for(j=0;j<nto[B];j++)
             {
                 h=to[B][j];
                 if(a[A][h])
                 {
                     push(A,h,0,cost+1,A,B,C);
                 }
                 else
                     push(A,h,1,cost+1,A,B,C);
             }

        }
        else
        if(C==1)
        {
             int lastB=pj[C][A][B];
			 for(j=0;j<nto[A];j++)
             {
                 g=to[A][j];
				 if(A==B&&lastB==g) continue;
                 if(a[g][B])
                 {
                     push(g,B,0,cost+1,A,B,C);
                 }
             }
        }
        else
        {
             int lastA=pi[C][A][B];
			 for(j=0;j<nto[B];j++)
             {
                 h=to[B][j];
				 if(A==B&&lastA==h) continue;
                 if(a[A][h])
                 {
                     push(A,h,0,cost+1,A,B,C);
                 }
             }
        }
  }
  cost=d[0][di][dj];
  m=0;
  i=di;j=dj; k=0;
  while(i!=si||j!=sj||k)
  {
  	wi[m]=i+1;
  	wj[m]=j+1;
  	wk[m]=k;
  	m++;
  	di=pi[k][i][j];
  	dj=pj[k][i][j];
  	t= pk[k][i][j];
  	i=di;
  	j=dj;
  	k=t;
  }
  	wi[m]=i+1;
  	wj[m]=j+1;
  	wk[m]=0;
  	m++;
  for(i=m-1,k=0;i>=0;i--)
   if(!wk[i]) k++;
  printf("%d %d\n",cost-1,k);
  for(i=m-1;i>=0;i--)
   if(!wk[i])
   printf("%d %d\n",wi[i],wj[i]);

  return 0;
}