void main(){
  import std.stdio, std.string, std.conv, std.algorithm;
 
  int n; rd(n);
  int m; rd(m);
 
  auto g=new int[][](n);
  foreach(i; 0..m){
    int a, b; rd(a, b);
    g[a-1]~=(b-1);
  }
 
  auto vis=new bool[](n), seq=new int[](0);
  bool multi=false;
  void dfs(int i){
    vis[i]=true;
    int cnt=0;
    foreach(j; g[i]){
      if(vis[j]) continue;
      cnt++; dfs(j);
    }
    if(cnt>1) multi=true;
    seq=i~seq;
  }
   
  foreach(i; 0..n)if(vis[i]==false) dfs(i);
  writefln("%(%s\n%)", seq.map!(i=>i+1));
  // if(multi) writeln(1);
  // else writeln(0);
  multi=false;
  foreach(i; 0..n)if(g[i].length>1) multi=true;
  if(multi) writeln(1);
  else writeln(0);
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}
