{
    ACM ICPC 2003-2004 NEERC

    Problem:    Bring Them There
    Author:     Alexander Klenin
    Solution:   Maxim Babenko
}

{$APPTYPE CONSOLE}

uses
    Math;

const
    inFile = 'bring.in';
    outFile = 'bring.out';

    maxN = 50;
    maxM = 200;
    maxK = 50;

    infinity = maxlongint div 4;

    maxT = maxN + maxK;
    maxE = maxN * (maxM + maxN);

type
    TEdge = record
        cap, flow : integer;
        tnode, ttime : integer;
        rev : integer;
    end;

    TVertex = record
        node, time : integer;
    end;

var
    n : integer;
    m : integer;
    g : array[1..maxN,1..maxN] of boolean;
    k : integer;
    s, t : integer;

    nout : array[1..maxN,0..maxT] of integer;
    e : array[1..maxN,0..maxT,1..maxN*2] of TEdge;

    tbound : integer;
    flow : integer;

    q : array[1..maxE] of TVertex;
    p : array[1..maxN,0..maxT] of integer;

procedure BuildGraph;
var
    i, j, q : integer;

    procedure MakeEdge(tnode1, ttime1, tnode2, ttime2 : integer; cap : integer);
    var
        i, j : integer;

    begin
        inc(nout[tnode1,ttime1]);
        i := nout[tnode1,ttime1];

        inc(nout[tnode2,ttime2]);
        j := nout[tnode2,ttime2];

        e[tnode1,ttime1,i].tnode := tnode2;
        e[tnode1,ttime1,i].ttime := ttime2;
        e[tnode1,ttime1,i].flow := 0;
        e[tnode1,ttime1,i].cap := cap;
        e[tnode1,ttime1,i].rev := j;

        e[tnode2,ttime2,j].tnode := tnode1;
        e[tnode2,ttime2,j].ttime := ttime1;
        e[tnode2,ttime2,j].flow := 0;
        e[tnode2,ttime2,j].cap := 0;
        e[tnode2,ttime2,j].rev := i;
    end;

begin
    fillchar(nout, sizeof(nout), 0);

    for i := 1 to n do
        for j := 0 to n + k - 1 do begin
            for q := 1 to n do
                if g[i,q] then
                    MakeEdge(i, j, q, j + 1, 1);
            MakeEdge(i, j, i, j + 1, infinity);
        end;
end;

procedure ExtendFlow;
var
    i : integer;

begin
    for i := 1 to nout[t,tbound] do
         if (e[t,tbound,i].tnode = t) and (e[t,tbound,i].ttime = tbound + 1) then begin
            e[t,tbound,i].flow := flow;
            e[t,tbound+1,e[t,tbound,i].rev].flow := -flow;
            inc(tbound);
            exit;
         end;
    RunError(241);
end;

function BFS : boolean;
var
    head, tail : integer;
    node, time : integer;
    i : integer;

begin
    head := 1;
    tail := 1;
    q[1].node := s;
    q[1].time := 0;
    fillchar(p, sizeof(p), 0);

    while head >= tail do begin
        node := q[tail].node;
        time := q[tail].time;
        inc(tail);

        if (node = t) and (time = tbound) then begin
            BFS := true;
            exit;
        end;

        for i := 1 to nout[node,time] do
            if (p[e[node,time,i].tnode, e[node,time,i].ttime] = 0) and
               (e[node,time,i].flow < e[node,time,i].cap) and
               (e[node,time,i].ttime <= tbound ) then begin
                inc(head);
                q[head].node := e[node,time,i].tnode;
                q[head].time := e[node,time,i].ttime;
                p[e[node,time,i].tnode, e[node,time,i].ttime] := e[node,time,i].rev;
            end;
    end;

    BFS := false;
end;

procedure Augment;
var
    node1, time1, node2, time2 : integer;
    i, j : integer;
    eps : integer;

begin
    eps := infinity;

    node1 := t;
    time1 := tbound;
    while (node1 <> s) or (time1 <> 0) do begin
        i := p[node1,time1];
        j := e[node1,time1,i].rev;
        node2 := e[node1,time1,i].tnode;
        time2 := e[node1,time1,i].ttime;
        eps := min(eps, e[node2,time2,j].cap - e[node2,time2,j].flow);
        node1 := node2;
        time1 := time2;
    end;
    
    node1 := t;
    time1 := tbound;
    while (node1 <> s) or (time1 <> 0) do begin
        i := p[node1,time1];
        j := e[node1,time1,i].rev;
        node2 := e[node1,time1,i].tnode;
        time2 := e[node1,time1,i].ttime;
        inc(e[node2,time2,j].flow, eps);
        dec(e[node1,time1,i].flow, eps);
        node1 := node2;
        time1 := time2;
    end;

    inc(flow, eps);
end;

procedure Solve;
begin
    BuildGraph;
    flow := 0;
    tbound := 0;
    while flow < k do begin
        ExtendFlow;
        while (flow < k) and BFS do
            Augment;
    end;
end;

procedure ReadData;
var
    i : integer;
    x, y : integer;

begin
    read(n);
    if (n < 1) or (n > maxN) then
        RunError(239);
    read(m);
    if (m < 1) or (m > maxM) then
        RunError(239);
    read(k);
    if (k < 1) or (k > maxK) then
        RunError(239);
    read(s, t);
    if (s < 1) or (s > n) or (t < 1) or (t > n) or (s = t) then
        RunError(239);

    fillchar(g, sizeof(g), false);
    for i := 1 to m do begin
        read(x, y);
        if (x < 1) or (x > n) or (y < 1) or (y > n) then
            RunError(239);
        if (x = y) or g[x,y] then
            RunError(239);
        g[x,y] := true;
        g[y,x] := true;
    end;

    close(input);
end;

procedure WriteData;
var
    i, j, q, r, count : integer;

    qu : array[1..maxN,1..maxK] of integer;
    head, tail : array[1..maxN] of integer;
    flow : array[1..maxN,1..maxN] of integer;

    procedure Insert(node : integer; value : integer);
    begin
        qu[node,head[node]] := value;
        inc(head[node]);
        if head[node] > k then
            head[node] := 1;
    end;

    function Extract(node : integer) : integer;
    begin
        Extract := qu[node,tail[node]];
        inc(tail[node]);
        if tail[node] > k then
            tail[node] := 1;
    end;

begin
    for i := 1 to n do begin
        head[i] := 1;
        tail[i] := 1;
    end;

    for i := 1 to k do
        Insert(s, i);

    writeln(tbound);
    for i := 1 to tbound do begin
        fillchar(flow, sizeof(flow), 0);
        for j := 1 to n do
            for q := 1 to nout[j,i-1] do
                if (e[j,i-1,q].tnode <> j) and (e[j,i-1,q].flow > 0) then begin
                    inc(flow[j, e[j,i-1,q].tnode], e[j,i-1,q].flow);
                    dec(flow[e[j,i-1,q].tnode, j], e[j,i-1,q].flow);
                end;

        count := 0;
        for j := 1 to n do
            for q := 1 to n do
                if flow[j,q] > 0 then
                    inc(count);

        write(count);
        for j := 1 to n do
            for q := 1 to n do
                if flow[j,q] > 0 then begin
                    r := Extract(j);
                    Insert(q, r);
                    write('  ', r, ' ', q);
                end;
        writeln;
    end;

    close(output);
end;

begin
    ReadData;
    Solve;
    WriteData;
end.
