#include <iostream>
#include <fstream>
#include <list>
#include <vector>

using namespace std;

ifstream fin( "kingdom.in" );
ofstream fout( "kingdom.out" );

const int MAX_N = 100;
const int INF = 10000000;

struct SPosition
{
   int A;
   int B;
};

bool operator != ( const SPosition &a, const SPosition &b )
{
   return a.A != b.A || a.B != b.B;
}

struct SCity
{
   vector<int> Portals;
};

struct SPair
{
   bool IsActive;
   bool IsVisited;
   int C;
   int K;
   SPosition Next;
};

int N, M;
SCity Cities[ 1 + MAX_N ];
SPair Pairs[ 1 + MAX_N ][ 1 + MAX_N ];
SPosition Start;
SPosition End;

list<SPosition> Queue0;
list<SPosition> Queue1;
list<SPosition> Queue2;

void FindPath( SPosition start )
{
   int i, j;

   Queue0.push_back( start );

   Pairs[ start.A ][ start.B ].C = 0;
   Pairs[ start.A ][ start.B ].K = 1;

   while( true )
   {
      /*list<SPosition>::iterator iter;

/      for( iter = Queue0.begin(); iter != Queue0.end(); iter++ )
      {
         cout << iter->A << " " << iter->B << ", ";
      }
      cout << endl;*/

      if( Queue0.empty() )
      {
         Queue0.assign( Queue1.begin(), Queue1.end() );
         Queue1.clear();
         Queue1.assign( Queue2.begin(), Queue2.end() );
         Queue2.clear();
      }

      if( Queue0.empty() )
      {
         Queue0.assign( Queue1.begin(), Queue1.end() );         
         Queue1.clear();
      }

      if( Queue0.empty() )
         return;

      SPosition pos = Queue0.front();
      Queue0.pop_front();      

      Pairs[ pos.A ][ pos.B ].IsVisited = true;

      vector<int> &APortals = Cities[ pos.A ].Portals;
      vector<int> &BPortals = Cities[ pos.B ].Portals;

      int maxi = APortals.size();
      int maxj = BPortals.size();

      for( i = 0; i < maxi; i++ )
      {
         if( Pairs[ APortals[ i ] ][ pos.B ].IsActive && 
            !Pairs[ APortals[ i ] ][ pos.B ].IsVisited &&
            Pairs[ APortals[ i ] ][ pos.B ].C > Pairs[ pos.A ][ pos.B ].C + 1 )
         {
            Pairs[ APortals[ i ] ][ pos.B ].C = Pairs[ pos.A ][ pos.B ].C + 1;
            Pairs[ APortals[ i ] ][ pos.B ].K = Pairs[ pos.A ][ pos.B ].K + 1;            
            Pairs[ APortals[ i ] ][ pos.B ].Next = pos;


            SPosition next;

            next.A = APortals[ i ];
            next.B = pos.B;

            Queue1.push_back( next );
         }
      }
      for( j = 0; j < maxj; j++ )
      {
         if( Pairs[ pos.A ][ BPortals[ j ] ].IsActive && 
            !Pairs[ pos.A ][ BPortals[ j ] ].IsVisited &&
            Pairs[ pos.A ][ pos.B ].C > Pairs[ pos.A ][ pos.B ].C + 1 )
         {
            Pairs[ pos.A ][ BPortals[ j ] ].C = Pairs[ pos.A ][ pos.B ].C + 1;
            Pairs[ pos.A ][ BPortals[ j ] ].K = Pairs[ pos.A ][ pos.B ].K + 1;
            Pairs[ pos.A ][ BPortals[ j ] ].Next = pos;


            SPosition next;

            next.A = pos.A;
            next.B = BPortals[ j ];

            Queue1.push_back( next );
         }
      }

      for( i = 0; i < maxi; i++ )
      {
         for( j = 0; j < maxj; j++ )
         {
            if( APortals[ i ] == pos.B && BPortals[ j ] == pos.A )
               continue;

            if( Pairs[ APortals[ i ] ][ BPortals[ j ] ].IsActive && 
               !Pairs[ APortals[ i ] ][ BPortals[ j ] ].IsVisited &&
               Pairs[ APortals[ i ] ][ BPortals[ j ] ].C > Pairs[ pos.A ][ pos.B ].C + 2 )
            {
               Pairs[ APortals[ i ] ][ BPortals[ j ] ].C = Pairs[ pos.A ][ pos.B ].C + 2;
               Pairs[ APortals[ i ] ][ BPortals[ j ] ].K = Pairs[ pos.A ][ pos.B ].K + 1;
               Pairs[ APortals[ i ] ][ BPortals[ j ] ].Next = pos;


               SPosition next;

               next.A = APortals[ i ];
               next.B = BPortals[ j ];

               Queue2.push_back( next );
            }
         }
      }
   }
}

void WritePath( SPosition start, SPosition end )
{
   fout << Pairs[ start.A ][ start.B ].C << " " << Pairs[ start.A ][ start.B ].K << endl;

   SPosition pos = start;

   while( pos != end )
   {
      fout << pos.A << " " << pos.B << endl;

      pos = Pairs[ pos.A ][ pos.B ].Next;
   } 

   fout << pos.A << " " << pos.B << endl;
}

void ReadData()
{
   int i, j;
   
   fin >> N >> M;

   fin >> Start.A >> Start.B;
   fin >> End.A >> End.B;

   for( i = 1; i <= N; i++ )
   {
      for( j = 1; j <= N; j++ )
      {
         Pairs[ i ][ j ].IsActive = false;
         Pairs[ i ][ j ].IsVisited = false;
         Pairs[ i ][ j ].C = INF;
         Pairs[ i ][ j ].K = INF;
      }
   }

   for( i = 1; i <= M; i++ )
   {
      int s, e;

      fin >> s >> e;

      Cities[ s ].Portals.push_back( e );
      Cities[ e ].Portals.push_back( s );

      Pairs[ s ][ e ].IsActive = true;
      Pairs[ e ][ s ].IsActive = true;
   }
}

void Work()
{
   FindPath( End );
}

void Output()
{
   WritePath( Start, End );
}

int main()
{
   ReadData();

   Work();

   Output();

   return 0;
}
