#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int fa[N + 10];
int n, m;
const int MOD = 1000000009;
int getf(int x) {
  if (x == fa[x]) return x;
  int t = getf(fa[x]);
  fa[x] = t;
  return t;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) fa[i] = i;
  long long ans = 1;
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    int x = getf(a);
    int y = getf(b);
    if (x == y) {
      ans = ans * 2 % MOD;
    } else
      fa[x] = y;
    printf("%I64d\n", (ans + MOD - 1) % MOD);
  }
  return 0;
}
