{$o-,q+,r+}
{ $o+,q-,r-}
{$MINSTACKSIZE $00004000}
{$APPTYPE console}
uses
    sysutils;
type
    int = longint;
    pair = array[1 .. 2] of int;
const
    finname = 'kingdom';
    maxm = 2010;
    inf = $77777777;
var
    n, m, i, j, a1, a2, b1, b2, s, t, qh, qt: int;
    q: array[1 .. maxm * maxm + 10] of int;
    r, b: array[1 .. maxm, 1 .. maxm] of boolean;
    a: array[1 .. maxm, 1 .. maxm] of int;
    bi: array[1 .. maxm, 1 .. 2] of int;
    aa, d, u, p: array[1 .. maxm] of int;
    na: int;
    im: int;
begin
    reset(input, finname + '.in');
    rewrite(output, finname + '.out');

    read(n, m, a1, b1, a2, b2);
    for i := 1 to n do
        for j := 1 to n do
            r[i, j] := (i = j);

    for i := 1 to m do begin
        read(bi[i, 1], bi[i, 2]);
        bi[i + m, 1] := bi[i, 2];
        bi[i + m, 2] := bi[i, 1];
        r[bi[i, 1], bi[i, 2]] := true;
        r[bi[i, 2], bi[i, 1]] := true;
    end;

    m := 2 * m;

    for i := 1 to m do
        for j := 1 to m do begin
            a[i, j] := inf;
            if (r[bi[i, 1], bi[j, 1]] and r[bi[i, 2], bi[j, 2]]) then
                a[i, j] := 2 - ord(bi[i, 1] = bi[j, 1]) - ord(bi[i, 2] = bi[j, 2]);
        end;

    for i := 1 to m do begin
        a[i, i + m div 2] := inf;
        a[i + m div 2, i] := inf;
    end;

    for i := 1 to m do begin
        if (bi[i, 1] = a1) and (bi[i, 2] = b1) then begin
            s := i;
        end;
        if (bi[i, 1] = a2) and (bi[i, 2] = b2) then begin
            t := i;
        end;
    end;

    for i := 1 to m do begin
        d[i] := inf;
        u[i] := 1;
    end;
    d[s] := 0;
    while true do begin
        im := -1;
        for i := 1 to m do
            if (u[i] = 1) and (d[i] < inf) and ((im = -1) or (d[i] < d[im])) then begin
                im := i;
                //break;
            end;
        if (im = -1) then
            break;
        u[im] := 0;
        for i := 1 to m do
            if (u[i] = 1) and (a[im, i] < inf) and (d[i] > d[im] + a[im, i]) then
                d[i] := d[im] + a[im, i];
    end;

    if (u[t] <> 0) then begin
        write('abacaba');
        exit;
    end;

    for i := 1 to m do
        for j := 1 to m do
            if (a[i, j] < inf) and (d[j] = d[i] + a[i, j]) then
                b[i, j] := true;

    for i := 1 to m do
        u[i] := inf;
    qt := 1;
    qh := 1;
    q[1] := s;
    u[s] := 1;
    while (qh >= qt) do begin
        i := q[qt];
        inc(qt);
        for j := 1 to m do
            if (u[j] = inf) and (b[i, j]) then begin
                u[j] := u[i] + 1;
                p[j] := i;
                inc(qh);
                q[qh] := j;
            end;
    end;

    na := 0;
    i := t;
    if u[t] = inf then
        while true do begin
        end;
    repeat
        inc(na);
        aa[na] := i;
        if (i = s) then
            break;
        i := p[i];
    until false;

    writeln(d[t], ' ', u[t]);
    for i := na downto 1 do
        writeln(bi[aa[i], 1], ' ', bi[aa[i], 2]);



end.