{$A+,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q-,R-,S-,T-,U-,V+,W-,X+,Y+,Z1}
{$MINSTACKSIZE $00004000}
{$MAXSTACKSIZE $00100000}
{$IMAGEBASE $00400000}
{$APPTYPE CONSOLE}

var qc:array[0..200,0..200,1..3]of longint;
    he:array[0..200,0..200]of longint;
    res:array[1..100000,1..2]of longint;
    i,j,k,l,n,m,a1,a2,b1,b2,num:longint;
begin
assign(input,'kingdom.in');
assign(output,'kingdom.out');
reset(input);
rewrite(output);
readln(n,m,a1,b1,a2,b2);
for i:=1 to m do
        begin
        readln(k,j);
        he[k,j]:=1;
        he[j,k]:=1;
        end;
for i:=1 to n do he[i,i]:=1;
fillchar(qc,sizeof(qc),0);
qc[a1,b1,1]:=1;
m:=0;
while qc[a2,b2,1]=0 do
        begin
        inc(m);
        for i:=1 to n do
                for j:=1 to n do
                        if qc[i,j,1]=m then
                                begin
                                for k:=1 to n do
                                        for l:=1 to n do
                                                if (((qc[k,l,1]=0))and(k<>l)) then
                                                begin
                                                if (((he[i,k]=1)and(he[j,l]=1)and(he[l,k]=1))and(not((i=l)and(j=k)))) then
                                                        begin
                                                        if ((k=i)or(j=l)) then
                                                                qc[k,l,1]:=m+1
                                                        else
                                                        if (qc[k,l,1]>qc[i,j,1]+1) then
                                                                begin
                                                                qc[k,l,1]:=m+2
                                                                end;
                                                        qc[k,l,2]:=i;
                                                        qc[k,l,3]:=j;
                                                        end;
                                                end;
                                end;
        end;
i:=a2;
j:=b2;
num:=0;
while not(qc[i,j,1]=1) do
        begin
        inc(num);
        res[num,1]:=i;
        res[num,2]:=j;
        k:=i;
        l:=j;
        i:=qc[k,l,2];
        j:=qc[k,l,3];
        end;
writeln(qc[a2,b2,1]-1,' ',num+1);
writeln(a1,' ',b1);
for i:=num downto 1 do
        writeln(res[i,1],' ',res[i,2]);
end.
