#include <assert.h>
#include <stdio.h>

#define for(what) if (0) ; else for(what)

struct Edge
{
  int from;
  int to;
  Edge* next;
  int data;
  Edge* prev;
  bool mark;

  Edge(int from, int to)
  {
    prev = 0;
    mark = false;
    data = -1;
    this->from = from;
    this->to = to;
  }
};

int n, m, a1, b1, a2, b2;
Edge* e[100];
Edge* e0[100][100];
Edge *start, *finish;

void add_edge(int a, int b)
{
  Edge* ee = new Edge(a,b);
  ee->next = e[a];
  e[a] = ee;
  e0[a][b] = ee;
}

void relax(Edge* e1, Edge* e2, int w)
{
  int t = e2->data+w;
  if ((e1->data==-1)||(e1->data>t))
  {
    e1->data = t;
    e1->prev = e2;
  }
}

int main()
{
  freopen("kingdom.in","rt",stdin);
  freopen("kingdom.out","wt",stdout);

  scanf("%d%d%d%d%d%d",&n,&m,&a1,&b1,&a2,&b2);
  for (int i=0;i<m;i++)
  {
    int a, b;
    scanf("%d%d",&a,&b);
    add_edge(a-1,b-1);
    add_edge(b-1,a-1);
  }
  start = e0[a1-1][b1-1];
  finish = e0[a2-1][b2-1];

  start->data = 0;
  Edge* cur = start;
  while (cur)
  {
    cur->mark = true;

    for (int a=0;a<n;a++)
      if (e0[cur->from][a]&&e0[cur->to][a])
      {
        relax(e0[cur->from][a],cur,1);
        relax(e0[a][cur->to],cur,1);
      }

    for (int i=0;i<n;i++)
      for (Edge* ee=e[i];ee;ee=ee->next)
        if (e0[cur->from][ee->from]&&e0[cur->to][ee->to]&&((cur->from!=ee->to)||(cur->to!=ee->from)))
          relax(ee,cur,2);

    cur = 0;
    for(int i=0;i<n;i++)
      for (Edge* ee=e[i];ee;ee=ee->next)
        if (!(ee->mark)&&(ee->data!=-1)&&(!cur||(cur->data>ee->data)))
          cur = ee;
  }

  assert(finish->data!=-1);
  int ws = 1;
  static Edge* w[10000];
  w[0] = finish;
  while (w[ws-1]!=start)
  {
    w[ws] = w[ws-1]->prev;
    ws++;
  }
  printf("%d %d\n",finish->data,ws);
  for (int i=ws-1;i>=0;i--)
    printf("%d %d\n",w[i]->from+1,w[i]->to+1);

  return 0;
}