program Project1;

{$APPTYPE CONSOLE}
{$O-,R+,S+,I+,Q+}

const
    FILE_IN = 'kingdom.in';
    FILE_OUT = 'kingdom.out';
    MAX_N = 100 + 2;
    KOEF = 10 + 10;

type
    PTReb = ^TReb;
    TReb = record
        x, y : byte;
        len : byte;
        next : PTReb;
    end;

var
    reb : array [1..MAX_N, 1..MAX_N] of PTReb;
    a : array [1..MAX_N, 1..MAX_N] of boolean;

    path : array [1..MAX_N, 1..MAX_N, 1..2] of longint;
    d : array [0..MAX_N, 0..MAX_N] of word;
    heap : array [0..MAX_N*MAX_N*KOEF, 1..2] of longint;

    visited : array [1..MAX_N] of boolean;
    a1, b1, a2, b2 : longint;
    n, m, i, j, q, w : longint;

procedure dijkstra;
var
    was : array [1..MAX_N, 1..MAX_N] of boolean;
    q, w : longint;
    count : longint;
    tmp : PTReb;

procedure add ( x, y : longint );
var
    k : longint;
begin
    inc ( count );
    k := count;
    while d[heap[k shr 1][1], heap[k shr 1][2]] > d[x, y] do
    begin
        heap[k] := heap[k shr 1]; 
        k := k shr 1;
    end;
    heap[k][1] := x;
    heap[k][2] := y;
end;

procedure get ( var x, y : longint );
var
    i, k : longint;
begin
    x := heap[1][1];
    y := heap[1][2];
    k := 1;
    while k shl 1 <= count do
    begin
        i := k shl 1;
        if ( i < count ) and ( d[heap[i][1],heap[i][2]] > d[heap[i+1][1],heap[i+1][2]] ) then
            inc ( i );
        heap[k] := heap[i];
        k := i;
    end;
    while d[heap[k shr 1][1], heap[k shr 1][2]] > d[heap[count][1],heap[count][2]] do
    begin
        heap[k] := heap[k shr 1];
        k := k shr 1;
    end;
    heap[k] := heap[count];
    dec ( count );
end;

begin
    fillchar ( was, sizeof ( was ), 0 );
    fillchar ( d, sizeof ( d ), 255 );
    d[a1, b1] := 0;
    count := 0;
    d[0,0] := 0;
    add ( a1, b1 );
    while not was[a2, b2] do
    begin
        repeat
            get ( q, w )
        until not was[q, w];
        was[q, w] := true;
        tmp := reb[q, w];
        while tmp <> nil do
        with tmp^ do
        begin
            if not was[x, y] then
            if d[x, y] > d[q, w] + len then
            begin
                path[x, y][1] := q;
                path[x, y][2] := w;
                d[x, y] := d[q, w] + len;
                add ( x, y );
            end;
            tmp := next;
        end;
    end;
end;

procedure addr ( x1, y1, x2, y2 : longint; length : byte );
var
    tmp : PTReb;
begin
    new ( tmp );
    with tmp^ do
    begin
        x := x2;
        y := y2;
        len := length;
        next := reb[x1, y1];
    end;
    reb[x1, y1] := tmp;
end;

procedure rec ( x, y, k : longint );
begin
    visited[x] := true;
    visited[y] := true;
    if ( x = a1 ) and ( y = b1 ) then
        writeln ( d[a2, b2], ' ', k )
    else
        rec ( path[x, y][1], path[x, y][2], k + 1 );
    writeln ( x, ' ', y );
end;

begin
    assign ( input, FILE_IN );
    assign ( output, FILE_OUT );
    reset ( input );
    readln ( n, m, a1, b1, a2, b2 );
    for i:=1 to m do
    begin
        read ( q ); read ( w );
        a[q, w] := true;
        a[w, q] := true;
    end;
    close ( input );
    
    for i:=1 to n do
        for j:=1 to n do
        if a[i, j] then
        for q:=1 to n do
            for w:=1 to n do
            if a[q, w] then
            begin
                if (i=q) and (j<>w) then
                if a[j, w] then
                    addr ( i, j, q, w, 1 );
                if (i<>q) and (j=w) then
                if a[i, q] then
                    addr ( i, j, q, w, 1 );
                if (i<>q) and (j<>w) then
                if (i<>w) or (j<>q) then 
                if a[i, q] and a[j, w] then
                    addr ( i, j, q, w, 2 );
            end;

    dijkstra;

    rewrite ( output );
    rec ( a2, b2, 1 );
    close ( output );
end.
