#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[100005];
int d[100005], lab[100005];
int go(int lev, int x) {
  d[x] = lev;
  for (int i = 0; i < (int)a[x].size(); i++) {
    if (d[a[x][i]]) return lev - d[a[x][i]] + 1;
    int j = 0;
    if ((j = go(lev + 1, a[x][i]))) return j;
  }
  return 0;
}
int u[100005], ucs = 0;
bool dfs(int x, int c, int s) {
  u[x] = ucs;
  lab[x] = c;
  c = (c + 1) % s;
  for (int i = 0; i < (int)a[x].size(); i++) {
    if (u[a[x][i]] != ucs) {
      if (dfs(a[x][i], c, s)) return 1;
    } else if (lab[a[x][i]] != c)
      return 1;
  }
  return 0;
}
bool test(int s) {
  memset(lab, 0, sizeof(lab));
  ++ucs;
  int flag = dfs(1, 0, s);
  if (flag) return false;
  return true;
}
int main(void) {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[x].push_back(y);
  }
  int cyc = go(1, 1), ans = 1;
  for (int i = 2; i <= cyc; i++) {
    if (cyc % i == 0) {
      for (int j = i; cyc % i == 0; j *= i) {
        if (test(j)) ans *= i;
        cyc /= i;
      }
      while (cyc % i == 0) cyc /= i;
    }
  }
  test(ans);
  printf("%d\n", ans);
  vector<int> ret;
  for (int i = 1; i <= n; i++)
    if (u[i] == ucs && lab[i] == 0) ret.push_back(i);
  printf("%d\n", (int)ret.size());
  for (int i = 0; i < (int)ret.size(); i++)
    printf("%d%c", ret[i], i == (int)ret.size() - 1 ? '\n' : ' ');
  return 0;
}
