#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[200][200];

int to[200][200];
int rt[101][101][101];
int nrt[200][200];

int nto[200];

int si,sj,di,dj;

int d[200][200];
int pi[200][200];
int pj[200][200];
int qi[20001];
int qj[20001];
int b,e;
int A,B;
void push(int i, int j, int cost, int A, int B)
{
    if(d[i][j]) return;
    pi[i][j]=A;
    pj[i][j]=B;
    qi[e]=i;
    qj[e]=j;
    d[i][j]=cost;
    e++;
    if(e==10001) e=0;
}

void push2(int i, int j)
{
    qi[e]=i;
    qj[e]=j;
    e++;
    if(e==10001) e=0;
}

bool pop(int& i, int& j, int& cost)
{
    if(b==e) return false;
    i=qi[b];
    j=qj[b];
    b++;
    if(b==10001) b=0;
    cost=d[i][j];
    return true;
}
int wi[30001];
int wj[30001];

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(nrt,0,sizeof(nrt));
  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,1,0,0);
  int cost;
  int h,g;
  int step=1;


  for(i=0;i<n;i++)
  {
     for(j=0;j<nto[i];j++)
     {
         g=to[i][j];
         for(k=0;k<nto[g];k++)
         {
            h=to[g][k];
            if(a[i][h])
             rt[i][g][nrt[i][g]++]=h;
         }
     }
  }
  while(pop(A,B,cost)&&!d[di][dj])
  {
         if(cost>step)
         {
         	push2(A,B);
         	continue;
         }

  	 for(i=0;i<nto[A];i++)
  	 {
  	     h=to[A][i];
  	     if(h!=B&&a[h][B])
  	     {
  	         push(h,B,cost+1,A,B);
  	     }
  	     if(h==B)
  	     {
  	          for(j=0;j<nto[B];j++)
  	          {
  	              g=to[B][j];
       	              if(h==B&&g==A) continue;
      	              push(h,g,cost+2,A,B);
  	          }
  	     }
  	     else
  	     for(j=nrt[h][B]-1;j>=0;j--)
  	     {
  	        g=rt[h][B][j];
                push(h,g,cost+2,A,B);
  	     }
  	 }
  	 for(i=0;i<nto[B];i++)
  	 {
  	     g=to[B][i];
  	     if(g!=A&&a[A][g])
  	     {
  	     	 push(A,g,cost+1,A,B);
  	     }
  	     
/*  	     for(j=nrt[A][g]-1;j>=0;j--)
  	     {
  	        h=rt[A][g][j];
  	        if(a[h][g])
  	        {
  	            if(h==B&&g==A) continue;
  	            push(h,g,cost+2,A,B);
  	        }
  	     }*/

  	 }
  	 step++;
  }
  cost=d[di][dj];
  m=0;
  i=di;j=dj;
  while(i!=si||j!=sj)
  {
  	wi[m]=i+1;
  	wj[m]=j+1;
  	m++;
  	di=pi[i][j];
  	dj=pj[i][j];
  	i=di;
  	j=dj;
  }
  	wi[m]=i+1;
  	wj[m]=j+1;
  	m++;

  printf("%d %d\n",cost-1,m);
  for(i=m-1;i>=0;i--)
   printf("%d %d\n",wi[i],wj[i]);

  return 0;
}