#include <bits/stdc++.h>
const int fin = 0, maxn = 200010, MC = 1000000009;
int N, M;
int p[maxn];
inline int getf(int x) {
  return p[x] = (p[x] != x && p[p[x]] != p[x]) ? getf(p[x]) : p[x];
}
int main() {
  if (fin) {
    freopen("t.in", "r", stdin);
    freopen("t.out", "w", stdout);
  }
  int ans = 1, x, y, i;
  scanf("%d%d", &N, &M);
  for (i = 1; i <= N; ++i) p[i] = i;
  while (M--) {
    scanf("%d%d", &x, &y);
    if (getf(x) == getf(y))
      ans = (ans << 1) % MC;
    else
      p[getf(y)] = getf(x);
    printf("%d\n", ans ? ans - 1 : MC);
  }
  if (fin) {
    fclose(stdin);
    fclose(stdout);
  }
  return 0;
}
