{
    ACM ICPC 2003-2004 NEERC

    Problem:    Bring Them There
    Author:     Alexander Klenin
    Solution:   Andrew Stankevich
}

{$APPTYPE CONSOLE}
{$DEFINE ALLOWMULTITEST}
{$O-,Q+,R+}

program bring_them_there;

uses
    sysutils, math;

const
    maxn = 50;
    maxm = 200;
    maxk = 50;
    maxe = maxn * 2 + maxm * 4;

var
    c, n, m, q, s, t, i, j, k, v, l, p, hd, tl: longint;
    lev, fval, dflow, tgf: longint;
    head: array [1..maxn] of longint;
    a: array [1..maxn, 1..maxn] of boolean;
    next, cap, delta, src, dst, rev: array [1..maxe] of longint;
    flow, from, can: array [1..maxe, 1..maxn + maxk] of longint;
    que: array [0..maxn * (maxn + maxk)] of record v, l: longint; end;
    ff: array [1..maxn, 1..maxn, 1..maxn + maxk] of longint;
    pos: array [1..maxk] of longint;
    visited: array [1..maxn] of boolean;

procedure dfs(x: longint);
var
    j: longint;
begin
    visited[x] := true;
    j := head[x];
    while j > 0 do
    begin
        if not visited[dst[j]] then
            dfs(dst[j]);
        j := next[j];
    end;
end;

begin
    if eoln then runerror(239);
    read(n);
    if eoln then runerror(239);
    read(m);
    if eoln then runerror(239);
    read(q);
    if eoln then runerror(239);
    read(s);
    if eoln then runerror(239);
    read(t);
    if not eoln then runerror(239);
    readln;
    if (n < 2) or (n > maxn) then runerror(239);
    if (m < 1) or (m > maxm) then runerror(239);
    if (q < 1) or (q > maxk) then runerror(239);
    if (s < 1) or (s > n) or (t < 1) or (t > n) or (s = t) then runerror(239);

    p := 0;
    for i := 1 to m do
    begin
        if eoln then runerror(239);
        read(j);
        if eoln then runerror(239);
        read(k);
        if not eoln then runerror(239);
        readln;

        if (j < 1) or (j > n) or (k < 1) or (k > n) or (j = k) then runerror(239);
        if a[j][k] then runerror(239);
        a[j][k] := true;
        a[k][j] := true;
        
        inc(p);
        next[p] := head[j];
        head[j] := p;
        cap[p] := 1;
        dst[p] := k;
        src[p] := j;
        delta[p] := 1;
        rev[p] := p + 1;

        inc(p);
        next[p] := head[k];
        head[k] := p;
        cap[p] := 0;
        dst[p] := j;
        src[p] := k;
        delta[p] := -1;
        rev[p] := p - 1;
        
        inc(p);
        next[p] := head[k];
        head[k] := p;
        cap[p] := 1;
        dst[p] := j;
        src[p] := k;
        delta[p] := 1;
        rev[p] := p + 1;

        inc(p);
        next[p] := head[j];
        head[j] := p;
        cap[p] := 0;
        dst[p] := k;
        src[p] := j;
        delta[p] := -1;
        rev[p] := p - 1;
    end;

    {$IFNDEF ALLOWMULTITEST}
    if not eof then runerror(239);
    {$ENDIF}

    fillchar(visited, sizeof(visited), 0);
    dfs(s);
    if not visited[t] then
        runerror(239);

    tgf := 0;
    for i := 1 to n do
    begin
        inc(p);
        next[p] := head[i];
        head[i] := p;
        cap[p] := q;
        dst[p] := i;
        src[p] := i;
        delta[p] := 1;
        rev[p] := p + 1;
        if i = t then
            tgf := p;

        inc(p);
        next[p] := head[i];
        head[i] := p;
        cap[p] := 0;
        dst[p] := i;
        src[p] := i;
        delta[p] := -1;
        rev[p] := p - 1;
    end;

    fval := 0;
    lev := 1;
    while fval < q do
    begin
        inc(lev);
        flow[tgf][lev - 1] := fval;
        flow[rev[tgf]][lev] := -fval;
        while fval < q do
        begin
            hd := 0;
            tl := 1;

            fillchar(que, sizeof(que), 0);

            que[hd].v := s;
            que[hd].l := 1;

            for i := 1 to n do
            begin
                for j := 1 to lev do
                    can[i][j] := -1;
            end;
            can[s][1] := q;

            while hd < tl do
            begin
                v := que[hd].v;
                l := que[hd].l;
                inc(hd);

                j := head[v];
                while j <> 0 do
                begin   
                    if (flow[j][l] < cap[j]) and (l + delta[j] >= 1) and (l + delta[j] <= lev) then
                    begin
                        if can[dst[j]][l + delta[j]] = -1 then
                        begin
                            can[dst[j]][l + delta[j]] := min(can[v][l], cap[j] - flow[j][l]);
                            from[dst[j]][l + delta[j]] := j;
                            que[tl].v := dst[j];
                            que[tl].l := l + delta[j];
                            inc(tl);
                        end;
                    end;
                    j := next[j];
                end;
            end;

            if can[t][lev] <= 0 then break;

            dflow := can[t][lev];
            if fval + dflow > q then
                dflow := q - fval;

            fval := fval + dflow;
            k := t;
            l := lev;
            while (k <> s) or (l <> 1) do
            begin
                j := l - delta[from[k][l]];
                inc(flow[from[k][l]][j], dflow);
                dec(flow[rev[from[k][l]]][l], dflow);
                k := src[from[k][l]];
                l := j;
            end;
        end;
        if (lev > n) and (fval = 0) then
            runerror(240);
    end;

    writeln(lev - 1);

    for i := 1 to n do
    begin
        j := head[i];
        while j > 0 do
        begin
            if delta[j] > 0 then
            begin
                for l := 1 to lev - 1 do
                begin
                    ff[i][dst[j]][l] := flow[j][l];
                end;
            end;
            j := next[j];
        end;
    end;

{
    for l := 1 to lev - 1 do
    begin
        writeln('day ', l);
        for i := 1 to n do
            for j := 1 to n do
                if ff[i][j][l] > 0 then
                    writeln(i, ' -> ', j, ' ', ff[i][j][l]);
    end;
}

    for i := 1 to n do
        for j := i + 1 to n do
            for l := 1 to lev - 1 do
            begin
                while (ff[i][j][l] > 0) and (ff[j][i][l] > 0) do
                begin
                    dec(ff[i][j][l]);
                    dec(ff[j][i][l]);
                    inc(ff[i][i][l]);
                    inc(ff[j][j][l]);
                end;
            end;

    for i := 1 to q do
        pos[i] := s;

    for i := 1 to lev - 1 do
    begin
        c := 0;
        for j := 1 to n do
            for k := 1 to n do
                if j <> k then
                    c := c + ff[j][k][i];

        write(c);
        for j := 1 to q do
        begin
            for k := 1 to n do
                if ff[pos[j]][k][i] > 0 then
                begin
                    if k <> pos[j] then
                    begin
                        write('  ', j, ' ', k);
                    end;
                    dec(ff[pos[j]][k][i]);
                    pos[j] := k;
                    break;
                end;
        end;
        writeln;
    end;

    for i := 1 to q do
        if pos[i] <> t then
            runerror(240);

    close(input);
    close(output);
end.