{super leafy tops of root vegetables!}
{$o-,q+,r+}
{$apptype console}
uses sysutils;
const MaxN=50;
      MaxTime=150;

var g:array [1..MaxN, 1..MaxN] of boolean;
    c, d:array [-1..MaxTime, 1..MaxN, 1..MaxN] of boolean;
    z:array [0..MaxTime, 1..MaxN, 1..MaxN] of extended;
    w, dw:array [-1..MaxTime, 1..MaxN] of integer;
    nm:array [-1..MaxTime, 1..MaxN, 1..MaxN] of integer;
    t, n, 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
        c[tm, v, i]:=false; c[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 f:array [0..MaxTime, 1..MaxN] of boolean;
    qx, qy, qp:array [1..100000] of 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;
    o:array [1..MaxN] of integer;
    qh, qt:integer;

function rec (x, y:integer):extended;
var i:integer;
begin
  if not qf[x, y] then begin
    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;
    if f[x-1, y] then
      qs[x, y]:=qs[x, y]+rec (x-1, y);
    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
    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;
    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;
    qfl[x, y]:=true;
  end;
  rec2:=ql[x, y];
end;

var i, j, l, m, k, s, x, y, mi, mj, cnt, maxt, maxtt, tmp, fndt, qtsav:integer;
    func, minfunc, currand, minrand:extended;
    fnd:boolean;

                      
label found;

begin
  randseed:=2391717;
  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;
  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] 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);


    {minfunc:=1e1000; qtsav:=-1;
    for i:=qt downto 1 do begin
      if qx[i]<fndt then break;
      if qy[i]=T then begin
        tmp:=i; func:=0;
        repeat
          j:=qy[tmp];
          mi:=qx[qp[tmp]]; mj:=qy[qp[tmp]];
          func:=func+z[mi, mj, j];
          tmp:=qp[tmp];
        until mi=0;
        if func<minfunc then begin
          minfunc:=func; qtsav:=i; minrand:=random;
        end else if func=minfunc then begin
          currand:=random;
          if currand<minrand then begin
            qtsav:=i; minrand:=currand;
          end;
        end;
      end;
    end;
    assert (qy[qtsav]=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;
  d:=c; dw:=w;
  for cc:=1 to k do poisk (0, s);
  writeln (maxtt);
  for l:=0 to maxtt-1 do begin
    cnt:=0; 
    for i:=1 to n do for j:=1 to n do 
      if c[l, i, j] then inc (cnt);
    write (cnt);
    for i:=1 to n do for j:=1 to n do
      if c[l, i, j] then write (' ', nm[l, i, j], ' ', j);
    writeln;
  end;
end.