#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> plist[MAXN];
int d[MAXN];
queue<int> q;
vector<int> ansv;
int ans;
int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  while (m--) {
    int x, y;
    scanf("%d%d", &x, &y);
    plist[x].push_back(y);
  }
  for (int i = 1; i <= n; i++) d[i] = INT_MAX;
  q.push(1);
  while (!q.empty()) {
    int nowp = q.front();
    q.pop();
    int val;
    if (nowp == 1 && d[nowp] == INT_MAX)
      val = 0;
    else
      val = d[nowp];
    for (vector<int>::iterator iter = plist[nowp].begin();
         iter != plist[nowp].end(); iter++) {
      int to = *iter;
      if (d[to] == -1)
        d[to] = val + 1, q.push(to);
      else if (d[to] > val + 1)
        d[to] = val + 1, q.push(to);
    }
  }
  ans = -1;
  for (int i = 1; i <= n; i++) {
    int nowp = i;
    if (d[nowp] == INT_MAX) continue;
    for (vector<int>::iterator iter = plist[nowp].begin();
         iter != plist[nowp].end(); iter++) {
      int to = *iter;
      if (d[to] == INT_MAX) continue;
      if (ans == -1)
        ans = abs(d[nowp] + 1 - d[to]);
      else
        ans = gcd(ans, abs(d[nowp] + 1 - d[to]));
    }
  }
  ansv.push_back(1);
  for (int i = 2; i <= n; i++)
    if (d[i] != INT_MAX && d[i] % ans == 0) ansv.push_back(i);
  printf("%d\n%d\n", ans, ansv.size());
  for (vector<int>::iterator iter = ansv.begin(); iter != ansv.end(); iter++)
    printf("%d ", *iter);
  return 0;
}
