{$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 GUI}
{$o-}
const
    max_n = 100;
    max_k = 100;
type
    tpath = array [0..max_n + max_k] of longint;
var
    i, i1, i2, j, k, l, q, n, m: longint;
    a: array [1..max_n, 1..max_n] of boolean;
    p1, p2: array [1..max_n + max_k, 1..max_n] of longint;
    z: array [1..max_n + max_k, 1..max_n, 1..max_n] of longint;
    s, t: longint;
    p: array [1..max_k] of tpath;

procedure search(i, j: longint);
var
    k: longint;
begin
    if i < l then begin
        for k := 1 to n do begin
            if a[j][k] and (p1[i + 1][k] = 0) and (z[i][j][k] = 0) then begin
                p1[i + 1][k] := i;
                p2[i + 1][k] := j;
                search(i + 1, k);
            end;
        end;
        if p1[i + 1][j] = 0 then begin
            p1[i + 1][j] := i;
            p2[i + 1][j] := j;
            search(i + 1, j);
        end;
    end;
    if i > 1 then begin
        for k := 1 to n do begin
            if (z[i - 1][k][j] <> 0) and (p1[i - 1][k] = 0) then begin
                p1[i - 1][k] := i;
                p2[i - 1][k] := j;
                search(i - 1, k);
            end;
        end;
    end;
end;

procedure push(q, i, j: longint);
var
    k: longint;
begin
    p[q][1] := s;
    for i := 1 to l - 1 do begin
        if z[i][j][j] > 0 then begin
            dec(z[i][j][j]);
        end else begin
            for k := 1 to n do begin
                if z[i][j][k] > 0 then begin
                    dec(z[i][j][k]);
                    j := k;
                    break;
                end;
            end;
        end;
        p[q][i + 1] := j;
    end;
end;

procedure fill(i, j: longint);
var
    ti, tj: longint;
begin
    while (i <> 1) or (j <> s) do begin
        ti := p1[i][j];
        tj := p2[i][j];

        if ti < i then begin
            {
            if (tj = 1) and (j = 3) or (j = 1) and (tj = 3) then begin
                writeln(ti, tj);
            end;
            }
            inc(z[ti][tj][j]);
        end else begin
            dec(z[i][j][tj]);
        end;

        i := ti;
        j := tj;
    end;
end;

procedure initSearch;
begin
    fillchar(p1, sizeof(p1), 0);
    fillchar(p2, sizeof(p2), 0);
    p1[1][s] := 1;
    search(1, s);
end;

var
    zz: longint;
    qq: array [1..max_k] of longint;
begin
    read(n, m, k, s, t);
    for i := 1 to m do begin
        read(j, l);
        a[j][l] := true;
        a[l][j] := true;
    end;

    q := 0;
    l := 1;
    initSearch;
    for l := 2 to n + k do begin
        for i := 1 to n do begin
            if p1[l - 1][i] <> 0 then begin
                search(l - 1, i);
            end;
       end;
        while (p1[l][t] <> 0) do begin
            fill(l, t);
            inc(q);
            if q = k then begin
                break;
            end;
            initSearch;
        end;
        if q = k then begin
            break;
        end;
    end;

    for i := 2 to l do begin
        z[i][t][t] := k;
    end;

    if q = k then begin
        for i := 1 to k do begin
            push(i, 1, s);
        end;
    end;

    for i := 1 to k do begin
        qq[i] := i;
    end;

    writeln(l - 1);
    for i := 2 to l do begin
        for i1 := 1 to k do begin
            for i2 := i1 + 1 to k do begin
                if (p[i1][i] <> p[i1][i - 1]) and (p[i1][i - 1] = p[i2][i]) and (p[i1][i] = p[i2][i - 1]) then begin
                    zz := qq[i1]; qq[i1] := qq[i2]; qq[i2] := zz;
                    p[i1][i - 1] := p[i1][i];
                    p[i2][i - 1] := p[i2][i];
                end;
            end;
        end;

        zz := 0;
        for j := 1 to k do begin
            if p[j][i] <> p[j][i - 1] then inc(zz);
        end;
        write(zz);
        for j := 1 to k do begin
            if p[j][i] <> p[j][i - 1] then write('  ', qq[j], ' ', p[j][i]);
        end;
        writeln;
    end;
    close(input);
    close(output);
end.