#include <bits/stdc++.h>
using namespace std;

vector <int> Graf[10011];
vector<bool> bejart;
vector<int> ans;
int m, n;
int eleres[10011];

void dfs(int v) {
  bejart[v] = true;
  for (int u : Graf[v]) {
    if (!bejart[u])
      dfs(u);
  }
  ans.push_back(v);
}

void topological_sort() {
  bejart.assign(n+1, false);
  ans.clear();
  for (int i = n; i > 0; i--) {
    if (!bejart[i])
      dfs(i);
    }
  reverse(ans.begin(), ans.end());
  for(int i=0; i<ans.size(); i++) {
    eleres[ans[i]]=i;
  }
}

int main() {
	cin>>n>>m;
  for (int i=1; i<=m; i++) {
    int a, b;
    cin>>a>>b;
    Graf[a].push_back(b);
  }
  topological_sort();
  for(int i=1; i<=n; i++) {
    for(int sz: Graf[i]) {
      if(eleres[i]>eleres[sz]) {
        cout<<0<<"\n";
        return 0;
      }
    }
  }
  int csere=-1;
  for(int i=1; i<n; i++){
    int a=ans[i-1], b=ans[i], lehet=1;
    for(int x : Graf[a]){
        if(x==b){
            lehet=0;
        }
    }
    if(lehet){
        csere=i-1;
    }
  }
  if(csere==-1){
    cout<<1<<"\n";
    for (int i=0; i<ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
  }
  else{
    cout<<2<<"\n";
    for (int i=0; i<ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    cout<<"\n";
    cerr<<csere;
    for (int i=0; i<ans.size(); i++) {
        if(i==csere){
            cout<<ans[i+1];
        }
        else if(i==csere+1){
            cout<<ans[i-1];
        }
        else{
            cout<<ans[i];
        }
        cout<<" ";
    }
    cout<<"\n";
  }
  return 0;
}