#include <bits/stdc++.h>
const int N = 100005;
const int MOD = 1000000009;
int f[N];
int find(int x) {
  if (x != f[x]) f[x] = find(f[x]);
  return f[x];
}
int main() {
  int i, n, m, x, y, a, b, r = 0;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) f[i] = i;
  while (m--) {
    scanf("%d%d", &a, &b);
    x = find(a);
    y = find(b);
    if (x == y) {
      r = (r + r + 1) % MOD;
    } else {
      f[y] = x;
    }
    printf("%d\n", r);
  }
  return 0;
}
