#include <bits/stdc++.h>
using namespace std;
struct Edge {
  int u, v, next;
} edge[1000010];
int head[100010];
int pos;
void insert(int x, int y) {
  edge[pos].u = x;
  edge[pos].v = y;
  edge[pos].next = head[x];
  head[x] = pos++;
}
int dep[100010];
void dfs(int now) {
  for (int i = head[now]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (dep[v] == -1) {
      dep[v] = dep[now] + 1;
      dfs(v);
    }
  }
}
int gcd(int x, int y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}
int color[100010];
int T;
void ddd(int now) {
  for (int i = head[now]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (color[v] == -1) {
      color[v] = (color[now] + 1) % T;
      ddd(v);
    }
  }
}
vector<int> f;
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  memset(head, 0, sizeof(head));
  pos = 1;
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    insert(x, y);
  }
  memset(dep, -1, sizeof(dep));
  dep[1] = 1;
  dfs(1);
  T = -1;
  for (int i = 1; i < pos; i++) {
    int x = edge[i].u;
    int y = edge[i].v;
    if (dep[x] == -1 || dep[y] == -1) continue;
    if (dep[x] == dep[y]) T = 1;
    int now = 0;
    if (dep[x] > dep[y]) now = dep[x] - dep[y] + 1;
    if (dep[x] < dep[y]) now = dep[y] - dep[x] - 1;
    if (now != 0) {
      if (T == -1)
        T = now;
      else
        T = gcd(T, now);
    }
  }
  memset(color, -1, sizeof(color));
  color[1] = 0;
  ddd(1);
  printf("%d\n", T);
  f.clear();
  for (int i = 1; i <= n; i++)
    if (color[i] == 0) f.push_back(i);
  int len = f.size();
  printf("%d\n", len);
  for (int i = 0; i < len; i++) printf("%d ", f[i]);
  return 0;
}
