#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:100000000")
using namespace std;
bool vis[100100];
vector<int> v[100100];
int d[100100];
void bfs() {
  queue<int> q;
  int dist = 0;
  q.push(1);
  d[1] = 0;
  vis[1] = true;
  while (!q.empty()) {
    dist++;
    for (int i = 0, maxi = (int)(q).size(); i < maxi; i++) {
      int s = q.front();
      q.pop();
      for (int j = 0, maxj = (int)(v[s]).size(); j < maxj; j++) {
        if (!vis[v[s][j]]) {
          vis[v[s][j]] = true;
          d[v[s][j]] = dist;
          q.push(v[s][j]);
        }
      }
    }
  }
}
int gcd(int a, int b) {
  if (!a) return b;
  return gcd(b % a, a);
}
vector<int> ans;
void go(int k) {
  queue<int> q;
  int dist = 0;
  q.push(1);
  ans.push_back(1);
  d[1] = 0;
  vis[1] = true;
  while (!q.empty()) {
    dist++;
    for (int i = 0, maxi = (int)(q).size(); i < maxi; i++) {
      int s = q.front();
      q.pop();
      for (int j = 0, maxj = (int)(v[s]).size(); j < maxj; j++) {
        if (!vis[v[s][j]]) {
          vis[v[s][j]] = true;
          d[v[s][j]] = dist;
          if (dist % k == 0) ans.push_back(v[s][j]);
          q.push(v[s][j]);
        }
      }
    }
  }
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    v[a].push_back(b);
  }
  bfs();
  int g = -1;
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) continue;
    for (int j = 0, maxj = (int)(v[i]).size(); j < maxj; j++) {
      int now = d[v[i][j]];
      int can = d[i] + 1;
      int diff = can - now;
      if (diff != 0) {
        if (g == -1)
          g = diff;
        else
          g = gcd(g, diff);
      }
    }
  }
  memset(vis, 0, sizeof(vis));
  if (g == -1) assert(0);
  go(g);
  printf("%d\n", g);
  printf("%d\n", (int)(ans).size());
  sort(ans.begin(), ans.end());
  for (int i = 0; i < (int)(ans).size(); i++) printf("%d ", ans[i]);
  return 0;
}
