// UUID: 8ed840b0-3aae-4daa-9b67-ce1667d01d46
#include <bits/stdc++.h>
#include <cctype>
#include <vector>
using namespace std;

void melysegi(vector<vector<int>> &memo, int v, vector<int> &tps, vector<bool> &done) {
	for (int i = 0;i < memo[v].size();i++) {
		if (!done[memo[v][i]]) {
			melysegi(memo, memo[v][i], tps, done);
			done[memo[v][i]] = true;
			tps.push_back(memo[v][i]);
		}
	}
}

int main() {
	int n,k;cin >> n >> k;
	vector<vector<int>> memo(n,vector<int>(0,0));
	int s = 0,l = 0;
	for (int i = 0;i < k;i++) {
		cin >> s >> l;
		memo[s - 1].push_back(l - 1);
	}
	/*
	for (int i = 0; i < n;i++) {
		for (int j = 0; j < memo[i].size();j++) {
			cout << memo[i][j] << " ";
		}
		cout << endl;
	}
	cout << "-------------------------" << endl;
	*/
	vector<bool> done(n + 1,false);
	vector<int> tps(0,0);
	for (int i = 0; i < n;i++) {
		if (!done[i]) {
			melysegi(memo, i, tps, done);
			done[i] = true;
			tps.push_back(i);
		}
	}
	reverse(tps.begin(), tps.end());
	int ans = 1;
	int swapplace = 0;
	if (done[n]) {
		cout << 0;
	}
	else {
		for (int i = 0;i < n - 1;i++) {
			if (find(memo[tps[i]].begin(), memo[tps[i]].end(), tps[i + 1]) == memo[tps[i]].end()) {
				ans++;
				swapplace = i;
				break;
			}
		}
		cout << ans << endl;
		for (int i:tps) {
			cout << i + 1 << " ";
		}
		cout << endl;
		if (ans == 2) {
			for (int i = 0;i < n;i++) {
				if (swapplace == i) {
					cout << tps[i + 1] + 1;
				}
				else {
					if (swapplace + 1 == i) {
						cout << tps[i - 1] + 1;
					}
					else {
						cout << tps[i] + 1;
					}
				}
			}
		}
	}
}