#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <functional>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <iomanip>

#define mp make_pair
#define i64 long long;
#define ui64 unsigned long long;

using namespace std;


struct Edge {
	int ind;
	int from;
	int to;
	int c;
	int f = 0;
	int back_edge;
};

vector<vector<Edge>> g;

int n, m, k, s, t;

vector<bool> was;

int dfs(int v, int flow, int konec) {
	if (v == konec) {
		return flow;
	}

	if (v / n > konec / n) {
		return 0;
	}

	was[v] = true;
	for (int i = 0; i < g[v].size(); ++i) {
		auto* e = &g[v][i];
		int to = -1;
		if (e->to == v) {
			to = e->from;
			if (!was[to] && e->f < e->c) {
				int del = dfs(to, min(flow, e->c - e->f), konec);
				if (del > 0) {
					e->f += del;
					g[to][e->back_edge].f -= del;
					return del;
				}
			}
		}
		else {
			to = e->to;
			if (!was[to] && e->f < e->c) {
				int del = dfs(to, min(flow, e->c - e->f), konec);
				if (del > 0) {
					e->f += del;
					g[to][e->back_edge].f -= del;
					return del;
				}
			}
		}
	}

	return 0;
}

vector<bool> www;
vector<vector<int>> g1;
int bfs(int v) {
	queue<pair<int, int>> q;
	q.push(mp(v, 0));
	while (!q.empty()) {
		auto pp = q.front();
		q.pop();
		www[pp.first] = true;
		if (pp.first == t) {
			return pp.second;
		}
		for (int i = 0; i < g1[pp.first].size(); ++i) {
			int to = g1[pp.first][i];
			if (!www[to]) {
				q.push(mp(to, pp.second + 1));
			}
		}
	}
}

int N = 0;

void build(int len) {
	N = n * (len + k - 1);
	g.resize(N);
	was.resize(N);
	for (int i = 0; i < len + k - 2; ++i) {
		for (int v = 0; v < n; ++v) {
			Edge e;
			e.f = 0;
			e.c = 1e9;
			e.from = v + i * n;
			e.to = v + (i + 1) * n;
			g[e.from].push_back(e);
			e.f = 1e9;
			g[e.to].push_back(e);
			g[e.from].back().back_edge = g[e.to].size() - 1;
			g[e.to].back().back_edge = g[e.from].size() - 1;
			for (int j = 0; j < g1[v].size(); ++j) {
				Edge e;
				e.f = 0;
				e.c = 1;
				e.from = v + i * n;
				e.to = g1[v][j] + (i + 1) * n;
				g[e.from].push_back(e);
				e.f = 1;
				g[e.to].push_back(e);
				g[e.from].back().back_edge = g[e.to].size() - 1;
				g[e.to].back().back_edge = g[e.from].size() - 1;
			}
		}
	}
}


int get_max_flow(int s, int en) {
	was.clear();
	was.resize(N);
	auto saved_graph = g;
	while (dfs(s, 1e9, en) > 0) {
		was.clear();
		was.resize(N);
	}
	int res = 0;
	for (int i = 0; i < g[s].size(); ++i) {
		res += g[s][i].f;
	}
	g = saved_graph;
	return res;
}

int main() {
#ifdef _KOCH
	freopen("input.txt", "r", stdin);
	// freopen("output3.txt", "w", stdout);
#else
	// freopen("dominoes.in", "r", stdin);
	// freopen("dominoes.out", "w", stdout);
#endif
	cin >> n >> m >> k >> s >> t;
	s--; t--;
	g1.resize(n);
	www.resize(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g1[a].push_back(b);
		g1[b].push_back(a);
	}

	int len = bfs(s);

	build(len + 1);

	int res = len - 1;
	for (int i = 0; k > get_max_flow(s, t + (len + i) *n); ++i) {
		res = len + i;
	}

	was.clear();
		was.resize(N);
	res++;
	while (dfs(s, 1e9, t + res * n) > 0) {
		was.clear();
		was.resize(N);
	}

	vector < vector<pair<int, int>>> ans(res);

	vector<vector<int>> sheep(n);

	int id = k;

	cout << res << endl;
	for (int l = 0; l < res; ++l) {
		vector<vector<int>> new_sheep(n);
		for (int i = 0; i < n; ++i) {
			int x = i + l*n;
			for (int j = 0; j < g[x].size(); ++j) {
				if (g[x][j].f == 1 && g[x][j].to % n != i && g[x][j].to != x) {
					if (!sheep[i].empty()) {
						ans[l].push_back(mp(sheep[i].back(), (g[x][j].to % n) + 1));
						new_sheep[g[x][j].to %n].push_back(sheep[i].back());
						sheep[i].pop_back();
					}
					else {
						if (id <= 0) {
							continue;
						}
						new_sheep[g[x][j].to % n].push_back(id--);
						ans[l].push_back(mp(id + 1, (g[x][j].to % n) + 1));
					}
				}
			}
		}
		sheep = new_sheep;
	}


	for (int i = 0; i < ans.size(); ++i) {
		cout << ans[i].size();
		for (int j = 0; j < ans[i].size(); ++j) {
			cout << "  " << ans[i][j].first << " " << ans[i][j].second;
		}
		cout << "\n";
	}
	return 0;
}