{$o+,q-,r-}
{$apptype console}
uses sysutils, windows;
const MaxN=50;
      MaxTime=150;

var g:array [1..MaxN, 1..MaxN] of boolean;
    c, d, oc:array [-1..MaxTime, 1..MaxN, 1..MaxN] of boolean;
    w, dw, ow:array [-1..MaxTime, 1..MaxN] of integer;
    nm:array [-1..MaxTime, 1..MaxN, 1..MaxN] of integer;
    mint, s, t, n, k:integer;



procedure display;
var cc:integer;
procedure poisk (tm, v:integer);
var i:integer;
begin
  if v=t then exit;
  for i:=1 to n do
    if d[tm, v, i] then begin
      d[tm, v, i]:=false; 
      if d[tm, i, v] then begin
        oc[tm, v, i]:=false; oc[tm, i, v]:=false;
        d[tm, i, v]:=false; inc (dw[tm, i]); poisk (tm+1, v) 
      end else begin
        poisk (tm+1, i); nm[tm, v, i]:=cc
      end; exit
    end;
  dec (dw[tm, v]); poisk (tm+1, v)
end;
var i, j, l, cnt:integer;

begin
  d:=oc; dw:=ow;
  for cc:=1 to k do poisk (0, s);
  writeln (mint);
  for l:=0 to mint-1 do begin
    cnt:=0; 
    for i:=1 to n do for j:=1 to n do 
      if oc[l, i, j] then inc (cnt);
    write (cnt);
    for i:=1 to n do for j:=1 to n do
      if oc[l, i, j] then write (' ', nm[l, i, j], ' ', j);
    writeln;
  end;
  halt;
end;


var f:array [0..MaxTime, 1..MaxN] of boolean;
    qx, qy, qp:array [1..100000] of integer;
    m, start, qh, qt:integer;


procedure firstsol;
var i, j, l, x, y, mi, mj, cnt, maxt, maxtt, tmp, fndt:integer;
    qs, ql:array [0..MaxTime, 1..MaxN] of extended;
    qf, qfl:array [0..MaxTime, 1..MaxN] of boolean;
    qpl:array [0..MaxTime, 1..MaxN] of integer;
    fnd:boolean;
function rec (x, y:integer):extended;
var i:integer;
begin
  if not qf[x, y] then begin
    if f[x-1, y] then
      qs[x, y]:=qs[x, y]+rec (x-1, y);
    for i:=1 to n do if f[x-1, i] and g[i, y] and not c[x-1, i, y] then begin
      qs[x, y]:=qs[x, y]+rec (x-1, i);
    end;
    qf[x, y]:=true;
  end;
  rec:=qs[x, y];
end;


function rec2 (x, y:integer):extended;
var i:integer;
    res:extended;
begin
  if not qfl[x, y] then begin
    if f[x-1, y] then begin
      res:=rec2 (x-1, y);
      if res+qs[x-1, y]<ql[x, y] then begin
        ql[x, y]:=res+qs[x-1, y];
        qpl[x, y]:=y;
      end;
    end;
    for i:=1 to n do if f[x-1, i] and g[i, y] and not c[x-1, i, y] then begin
      res:=rec2 (x-1, i);
      if res+qs[x-1, i]<ql[x, y] then begin
        ql[x, y]:=res+qs[x-1, i];
        qpl[x, y]:=i;
      end;
    end;
    qfl[x, y]:=true;
  end;
  rec2:=ql[x, y];
end;

begin
  cnt:=0; maxtt:=0;
  repeat
    fillchar (f, sizeof (f), 0);
    fillchar (qs, sizeof (qs), 0);
    qh:=1; qt:=2; f[0, s]:=true; qy[1]:=s; fnd:=false; fndt:=-1; 
    repeat
      x:=qx[qh]; y:=qy[qh];
      if fnd and (x=fndt) then break;
      for i:=1 to n do begin
        if g[y, i] and not c[x, y, i] and not c[x, i, y] then begin
          if not f[x+1, i] then begin
            f[x+1, i]:=true; qx[qt]:=x+1; qy[qt]:=i; qp[qt]:=qh;
            if i=T then begin fnd:=true; fndt:=x+1 end;
            inc (qt);
          end;
        end;
      end;
      if not f[x+1, y] then begin
        f[x+1, y]:=true; qx[qt]:=x+1; qy[qt]:=y; qp[qt]:=qh; inc (qt);
      end;
      inc (qh);
    until qh=qt;
    assert (qh<qt);
    dec (qt);

    for i:=0 to fndt do fillchar (qf[i], N, 0);
    for i:=0 to fndt do fillchar (qs[i], N*sizeof (extended), 0);
    for i:=0 to fndt do fillchar (qfl[i], N, 0);
    for i:=0 to fndt do
      for j:=1 to n do ql[i, j]:=1e1000;
    qf[0, s]:=true; qs[0, s]:=1;
    qfl[0, s]:=true; ql[0, s]:=0;
    rec (fndt, T);
    rec2 (fndt, T);
    if fndt>maxtt then maxtt:=fndt;
    i:=fndt; j:=T;
    repeat
      mi:=i-1; mj:=qpl[i, j];
      if mj=j then inc (w[mi, j])
              else c[mi, mj, j]:=true;
      i:=mi; j:=mj;
    until mi=0;
    inc (cnt);
  until cnt=k;
  mint:=maxtt; oc:=c; ow:=w;
end;




procedure randomsol;
var o:array [1..MaxN] of integer;
    i, j, l, x, y, mi, mj, cnt, maxt, maxtt, tmp:integer;
label found;
begin
  repeat
    fillchar (c, sizeof (c), 0);
    fillchar (w, sizeof (w), 0);
    cnt:=0; maxtt:=0;
    for i:=1 to n do begin tmp:=random (i)+1; o[i]:=o[tmp]; o[tmp]:=i end;
    repeat
      if GetTickCount-start>=1900 then display;
      fillchar (f, sizeof (f), 0);
      qh:=1; qt:=2; f[0, s]:=true; qy[1]:=s;
      repeat
        x:=qx[qh]; y:=qy[qh];
        for i:=1 to n do begin
          tmp:=o[i];
          if not f[x+1, tmp] and g[y, tmp] and not c[x, y, tmp] then begin
            f[x+1, tmp]:=true; qx[qt]:=x+1; qy[qt]:=tmp; qp[qt]:=qh; 
            if tmp=T then goto found;
            inc (qt);
          end;
        end;
        if not f[x+1, y] then begin
          f[x+1, y]:=true; qx[qt]:=x+1; qy[qt]:=y; qp[qt]:=qh; inc (qt);
        end;
        inc (qh);
      until qh=qt;
      found:
      assert (qy[qt]=t);
      if qx[qt]>maxtt then maxtt:=qx[qt];
      repeat
        j:=qy[qt];
        mi:=qx[qp[qt]]; mj:=qy[qp[qt]];
        if mj=j then inc (w[mi, j])
                else c[mi, mj, j]:=true;
        qt:=qp[qt];
      until mi=0;
      inc (cnt);
    until cnt=k;
    if maxtt<mint then begin mint:=maxtt; oc:=c; ow:=w end;
  until false;
end;


                      
label found;

var i, x, y:integer;

begin
  start:=GetTickCount;
  read (n, m, k, s, t);
  for i:=1 to m do begin
    read (x, y); g[x, y]:=true; g[y, x]:=true;
  end;
  firstsol; randomsol;
end.