kusrach

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>

using namespace std;

#define forn(i, n) for(size_t i = 0; i < (n); i++)
#define mp make_pair
typedef pair<int, bool> pib;
typedef pair<int, int> pii;

const int inf = 1000000000;

vector<vector<int> > g;
vector<vector<int> > gtr;
vector<vector<int> > paths;
vector<int> dots;
int n, m;

void front_find(int u, vector<int> &d, vector<bool> &used, queue<pib> &q, bool stop) {

	if (stop) return;

	for (size_t i = 0; i < g[u].size(); ++i) {

		int to = g[u][i];
		if (d[to] == inf) {
			d[to] = d[u] + 1;
			paths[to].push_back(u);
			used[to] = true;
			q.push(mp(to, true));
		}
		else if (d[u] + 1 == d[to])
			paths[to].push_back(u);
	}
}

void back_find(int u, vector<int> &d, vector<bool> &used, queue<pib> &q, bool &stop) {

	for (size_t i = 0; i < gtr[u].size(); ++i) {

		int to = gtr[u][i];
		if (used[to]) {
			paths[u].push_back(to);	// Сомнительный момент, ответ из-за этого дублируется иногда
			dots.push_back(to + 1);
			stop = true;
			continue;
		}
		if (d[to] == inf && !stop) {
			d[to] = d[u] + 1;
			paths[u].push_back(to);
			q.push(mp(to, false));
		}
	}
}

void find_path(int s, int f) {

	queue<pib> q;
	vector<int> d(n, inf);
	vector<int> dtr(n, inf);
	paths.resize(n, vector<int>());
	bool stop = false;

	vector<bool> used(n);

	used[s] = true;
	used[f] = true;

	d[s] = 0;
	dtr[f] = 0;

	q.push(mp(s, true));
	q.push(mp(f, false));
	while (!q.empty()) {
		pib u = q.front();
		q.pop();

		if (u.second)
			front_find(u.first, d, used, q, stop);
		else
			back_find(u.first, dtr, used, q, stop);
	}
}
int dp = 0;
void create_paths(int u, vector<vector<int> > &result, vector<int> &arr, int deep) {

	arr.push_back(u + 1);
	for (size_t i = 0; i < paths[u].size(); i++) {
		int to = paths[u][i];
		create_paths(to, result, arr, deep + 1);
	}
	dp = max(dp, deep);
	if (dp == deep)
		result.push_back(arr);
	arr.pop_back();
}

void vec_print(vector<int>::iterator begin, vector<int>::iterator end) {

	for (auto it = begin; it != end; it++)
		cout << *it << " ";
	cout << endl;
}

int main() {
//#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
//#endif
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	int v1, v2;
	cin >> v1 >> v2;
	v1--, v2--;

	g.resize(n, vector<int>());
	gtr.resize(n, vector<int>());

	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		g[x].push_back(y);
		gtr[y].push_back(x);
	}

	find_path(v1, v2);

	vec_print(dots.begin(), dots.end());

	vector<vector<int> > result;
	vector<int> temp;
	int deep = 0;

	create_paths(v2, result, temp, deep);

	for (size_t i = 0; i < result.size(); i++)
		vec_print(result[i].begin(), result[i].end());

	return 0;
}

/*
input.txt
9 16
1 9
1 2
1 4
2 3
2 5
2 6
3 1
3 8
4 3
5 6
5 7
6 7
6 8
7 8
8 4
8 9
9 6
*/

/*
output.txt
3 6
9 8 3 2 1
9 8 3 4 1
9 8 6 2 1
*/