{$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;
    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;
    qh, qt:integer;
    i, j, l, m, k, s, x, y, mi, mj, cnt, maxt, maxtt:integer;
                      
label found;

begin
  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);
    qh:=1; qt:=2; f[0, s]:=true; qy[1]:=s;
    repeat
      x:=qx[qh]; y:=qy[qh];
      for i:=1 to n do if not f[x+1, i] and g[y, i] and not c[x, y, i] then begin
        f[x+1, i]:=true; qx[qt]:=x+1; qy[qt]:=i; qp[qt]:=qh; 
        if i=T then goto found;
        inc (qt);
      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;
  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.