#include <bits/stdc++.h>
using namespace std;
vector<int> graph[100010];
int x[100010];
void dfs(int v, int c) {
  if (x[v] != -1) return;
  x[v] = c;
  int i;
  for ((i) = 0; (i) < (int)(graph[v].size()); (i)++) dfs(graph[v][i], c + 1);
}
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
int main(void) {
  int N, M, i, j, a, b, g = 0;
  scanf("%d%d", &N, &M);
  for ((i) = 0; (i) < (int)(M); (i)++) {
    scanf("%d%d", &a, &b);
    a--;
    b--;
    graph[a].push_back(b);
  }
  for ((i) = 0; (i) < (int)(N); (i)++) x[i] = -1;
  dfs(0, 0);
  for ((i) = 0; (i) < (int)(N); (i)++)
    for ((j) = 0; (j) < (int)(graph[i].size()); (j)++) {
      a = i;
      b = graph[i][j];
      if (x[a] != -1 && x[b] != -1) {
        int tmp = x[b] - x[a] - 1;
        if (tmp < 0) tmp = -tmp;
        if (tmp != 0) g = gcd(g, tmp);
      }
    }
  printf("%d\n", g);
  int cnt = 0;
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (x[i] != -1 && x[i] % g == 0) cnt++;
  printf("%d\n", cnt);
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (x[i] != -1 && x[i] % g == 0) {
      cnt--;
      printf("%d", i + 1);
      if (cnt == 0)
        printf("\n");
      else
        printf(" ");
    }
  return 0;
}
