import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class CountingStar {
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    static class DirectedEdge {
        int from;
        int to;
        int c;
        int flow;
        DirectedEdge reversedEdge;
        boolean visited = false;

        public DirectedEdge(int from, int to, int c) {
            this.from = from;
            this.to = to;
            this.c = c;
            this.flow = 0;
            reversedEdge = null;
        }
    }

    static class Query {
        int a;


        int b;

        public Query(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        int c;

    }

    static class Ship {
        int number;

        public Ship(int number, int to) {
            this.number = number;
            this.to = to;
        }

        int to;
    }

    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int source1 = scanner.nextInt() - 1;
        int sink1 = scanner.nextInt() - 1;
        ArrayDeque<Integer>[] to1 = new ArrayDeque[n];
        for (int i = 0; i < n; i++) {
            to1[i] = new ArrayDeque<>();
        }
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt() - 1;
            int b = scanner.nextInt() - 1;
            to1[a].addLast(b);
            to1[b].addLast(a);
        }
        int L = shortestPath(to1, source1, sink1);
        ArrayDeque<Query> queries = new ArrayDeque<>();

        for (int i = 0; i < (L + k - 1); i++) {
            for (int j = 0; j < n; j++) {
                queries.addLast(new Query(i * n + j, (i + 1) * n + j, Integer.MAX_VALUE));
                for (int to : to1[j]
                ) {
                    queries.addLast(new Query(i * n + j, (i + 1) * n + to, 1));
                }
            }
            int level = i + 1;
            if (level >= L) {
                int source = source1;
                int sink = level * n + sink1;
                ArrayDeque<DirectedEdge>[] to = new ArrayDeque[level * n + n];
                for (int j = 0; j < to.length; j++) {
                    to[j] = new ArrayDeque<>();
                }
                for (Query query : queries) {
                    int a = query.a;
                    int b = query.b;
                    int c = query.c;
                    DirectedEdge edge1 = new DirectedEdge(a, b, c);
                    DirectedEdge reversedEdge1 = new DirectedEdge(b, a, 0);
                    edge1.reversedEdge = reversedEdge1;
                    reversedEdge1.reversedEdge = edge1;
                    to[a].addLast(edge1);
                    to[b].addLast(reversedEdge1);
                }
                boolean[] mark = new boolean[to.length];
                int maxFlow = 0;
                while (true) {
                    Arrays.fill(mark, false);
                    int delta = dfs(source, Integer.MAX_VALUE, mark, to, sink);
                    if (delta > 0) {
                        maxFlow += delta;
                        if (maxFlow >= k) break;
                    } else {
                        break;
                    }
                }
                if (maxFlow >= k) {
                    System.out.println(level);
                    ArrayDeque<Integer>[] shipsOnStar = new ArrayDeque[n];
                    for (int j = 0; j < n; j++) {
                        shipsOnStar[j] = new ArrayDeque<>();
                    }
                    for (int j = 0; j < k; j++) {
                        shipsOnStar[source].addLast(j);
                    }
                    for (int curLevel = 0; curLevel < level; curLevel++) {
                        ArrayDeque<Ship> ships = new ArrayDeque<>();
                        for (int j = 0; j < n; j++) {
                            for (DirectedEdge toEdge : to[curLevel * n + j]
                            ) {
                                if (toEdge.flow == 1 && toEdge.c != Integer.MAX_VALUE) {
                                    if (shipsOnStar[toEdge.from - n * (curLevel)].size() == 0) continue;

                                    int shipLeft = shipsOnStar[toEdge.from - n * (curLevel)].removeFirst();
                                    ships.addLast(new Ship(shipLeft, toEdge.to - n * (curLevel + 1)));
                                }
                            }
                        }
                        System.out.print(ships.size());
                        for (Ship ship : ships
                        ) {
                            shipsOnStar[ship.to].addLast(ship.number);
                            System.out.print("  " + (ship.number + 1) + " " + (ship.to + 1));
                        }
                        System.out.print(System.lineSeparator());
                    }
                    break;
                }

            }


        }


    }

    private static int dfs(int v, int delta, boolean[] mark, ArrayDeque<DirectedEdge>[] to, int sink) {
        if (mark[v]) return 0;
        mark[v] = true;
        if (v == sink) return delta;
        for (DirectedEdge toEdge : to[v]
        ) {
            if (toEdge.flow < toEdge.c) {
                int deltaNew = dfs(toEdge.to, Math.min(delta, toEdge.c - toEdge.flow), mark, to, sink);
                if (deltaNew > 0) {
                    toEdge.flow += deltaNew;
                    toEdge.reversedEdge.flow = -toEdge.flow;
                    return deltaNew;
                }
            }
        }
        return 0;
    }

    private static int shortestPath(ArrayDeque<Integer>[] to1, int source1, int sink1) {
        ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();
        boolean[] visited = new boolean[to1.length];
        arrayDeque.addLast(source1);
        visited[source1] = true;
        int[] from = new int[to1.length];
        Arrays.fill(from, -1);
        while (!arrayDeque.isEmpty()) {
            int cur = arrayDeque.removeFirst();
            for (int to : to1[cur]
            ) {
                if (!visited[to]) {
                    visited[to] = true;
                    arrayDeque.addLast(to);
                    from[to] = cur;
                    if (to == sink1) break;
                }
            }
            if (from[sink1] != -1) break;
        }
        if (from[sink1] == -1) return -1;
        int cur = sink1;
        int length = 0;
        while (cur != source1) {
            length++;
            cur = from[cur];
        }
        return length;
    }
}