// UUID: 9256c001-ea02-451b-9ef1-210f86364e6d
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,k;cin >> n >>k;
	vector<int>a(n+1,0);
	vector<vector<int>>b(n+1);
	for(int i = 0; i < k;i++){
		int u,p; cin >> u >> p;
		b[u].push_back(p);
		a[p]++;
	}
	queue<int>q;
	vector<vector<int>>ki(2);
	for(int i = 1; i <= n;i++){
		if(a[i] == 0){
			q.push(i);
		}
	}
	bool tobb = false;
	while(!q.empty()){
		int most = q.front();
		q.pop();
		if(tobb == false&&q.size()>1){
			tobb = true;
			ki[1] = ki[0];
			ki[0].push_back(most);
			for(int i : b[most]){
			a[i]--;
				if(a[i] == 0){
					q.push(i);
				}
			}
			most=q.front();
			q.pop();
			ki[1].push_back(most);
			ki[1].push_back(ki[0][ki[0].size()-1]);

		}
		ki[0].push_back(most);
		for(int i : b[most]){
			a[i]--;
			if(a[i] == 0){
				q.push(i);
			}
		}
	}
	if(ki[0].size() != n){
		cout << "0";
		return 0;
	}
	
	if(tobb){
		for(int i = ki[1].size()-1; i < n;i++){
			ki[1].push_back(ki[0][i]);
		}
		cout << "2\n";
		for(int i = 0; i < n;i++){
			cout << ki[0][i] << " ";
		}
		cout << "\n";
		for(int i = 0; i < n;i++){
			cout << ki[1][i] << " ";
		}
	}else{
		cout << "1\n";
		for(int i = 0; i < n;i++){
			cout << ki[0][i] << " ";
		}
	}

}