#include <bits/stdc++.h>
using namespace std;
int nod(int a, int b) {
  while (a && b) {
    int c = a % b;
    a = b;
    b = c;
  }
  return a | b;
}
int Abs(int a) { return a >= 0 ? a : -a; }
int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int> > e(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    e[a].push_back(b);
  }
  vector<int> d(n, -1);
  queue<int> q;
  q.push(0);
  d[0] = 0;
  int r = 0;
  while (!q.empty()) {
    int i = q.front();
    q.pop();
    int dd = d[i] + 1;
    for (int j = 0; j < (int)e[i].size(); ++j) {
      int a = e[i][j];
      if (d[a] >= 0)
        r = nod(r, Abs(d[a] - dd));
      else {
        q.push(a);
        d[a] = dd;
      }
    }
  }
  int c = 0;
  for (int i = 0; i < n; ++i)
    if (d[i] >= 0 && d[i] % r == 0) c++;
  printf("%d\n%d\n", r, c);
  for (int i = 0; i < n; ++i)
    if (d[i] >= 0 && d[i] % r == 0) printf("%d ", i + 1);
  return 0;
}
