#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <math.h>
#include <queue>
#include <functional>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

#define REP(i,n) for (int i = 0; i < (n); i++)
#define IREP(i,n) for (i = 0; i < (n); i++)

typedef pair<int, pair<int,int> > item;
priority_queue<item, vector<item>, greater<item> > q;
vector<vector<bool> > was(105, vector<bool>(105,false));
vector<vector<int> > A(105, vector<int>(105,0));
vector<vector<int> > min(105, vector<int>(105,1000000));
vector<vector<int> > B(105);
vector<vector<pair<int,int> > > Prev(105, vector<pair<int,int> >(105,make_pair(-1,-1)));

void Add(int a,int b, int preva, int prevb)
{
   if (A[a][b] == 1 && a != b && !was[a][b])
      if (a != prevb || b != preva)
      {
         int qq = int(preva != a)+int(prevb != b);
         if (min[a][b] > min[preva][prevb]+qq)
         {
            min[a][b] = min[preva][prevb]+qq;
            q.push(make_pair(min[a][b], make_pair(a,b)));
            Prev[a][b] = make_pair(preva,prevb);
         }
      }
}

int main()
{
   ifstream ifs("kingdom.in");
   ofstream ofs("kingdom.out");
   int i,j,n,m;
   ifs >> n >> m;
   int a1,b1,a2,b2;
   ifs >> a1 >> b1 >> a2 >> b2;
   --a1; --a2; --b1; --b2;
   for (i = 0; i < m; ++i)
   {
      int v,w;
      ifs >> v >> w;
      --v; --w;
      A[v][w] = 1; A[w][v] = 1;
      B[v].push_back(w);
      B[w].push_back(v);
   }

   min[a1][b1] = 0;
   q.push(make_pair(0, make_pair(a1,b1)));
   while (!q.empty())
   {
      int a,b,l;
      a = q.top().second.first;
      b = q.top().second.second;
      l = q.top().first;
      q.pop();
      if (!was[a][b])
      {
         was[a][b] = true;
         if (a == a2 && b == b2)
         {
              break; 
         }
         int sa = B[a].size();
         for (i = 0; i < sa; ++i)
         {
            int nexta = B[a][i];
            Add(nexta,b,a,b);
         }
         int sb = B[b].size();
         for (i = 0; i < sb; ++i)
         {
            int nextb = B[b][i];
            Add(a,nextb,a,b);
         }
         for (i = 0; i < sa; ++i)
            for (j = 0; j < sb; ++j)
               Add(B[a][i],B[b][j],a,b);
      }
   }
   int cnt = min[a2][b2];
   vector<pair<int,int> > way;
   while (a2 >= 0)
   {
      way.push_back(make_pair(a2,b2));
      int na,nb;
      na = Prev[a2][b2].first;    
      nb = Prev[a2][b2].second;
      a2 = na;
      b2 = nb;
   }
   ofs << cnt << " " << way.size() << endl;
   for (i = way.size()-1; i >= 0; --i)
      ofs << way[i].first+1 << " " << way[i].second+1 << endl;
   return 0;
} 