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, q:array [-1..MaxTime, 1..MaxN] of boolean;
    p, pdt:array [-1..MaxTime, 1..MaxN] of 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);
    fillchar (q, sizeof (q), 0);
    f[0, s]:=true; q[0, s]:=true; maxt:=0;
    repeat
      mi:=-1; mj:=-1;
      for i:=0 to maxt do 
        for j:=1 to n do if q[i, j] then begin
          mi:=i; mj:=j; goto found;
        end;
      found:
      if mj=t then break;
      q[mi, mj]:=false;
      for j:=1 to n do
        if g[mj, j] then begin
          if not f[mi-1, j] and c[mi-1, j, mj] then begin
            f[mi-1, j]:=true; q[mi-1, j]:=true;
            p[mi-1, j]:=mj; pdt[mi-1, j]:=-1;
          end;
          if not f[mi+1, j] and not c[mi, mj, j] then begin
            if mi>=maxt then maxt:=mi+1;
            f[mi+1, j]:=true; q[mi+1, j]:=true;
            p[mi+1, j]:=mj; pdt[mi+1, j]:=1;
          end;
        end;
      if not f[mi-1, mj] and (w[mi-1, mj]>0) then begin
        f[mi-1, mj]:=true; q[mi-1, mj]:=true;
        p[mi-1, mj]:=mj; pdt[mi-1, mj]:=-1;
      end;
      if not f[mi+1, mj] then begin
        if mi>=maxt then maxt:=mi+1;
        f[mi+1, mj]:=true; q[mi+1, mj]:=true;
        p[mi+1, mj]:=mj; pdt[mi+1, mj]:=1;
      end;
    until false;
    inc (cnt); if mi>maxtt then maxtt:=mi;
    repeat
      i:=mi; j:=mj;
      mi:=mi-pdt[i, j]; mj:=p[i, j];
      if mj=j then
        if mi<i then inc (w[mi, j]) else dec (w[i, j])
      else
        if mi<i then c[mi, mj, j]:=true else c[i, j, mj]:=false;
    until mi=0;
  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.