#include <bits/stdc++.h>
const long long MOD = 1000000009LL;
int p[100010];
int find(int x) {
  if (x == p[x]) return x;
  return p[x] = find(p[x]);
}
int main() {
  int n, m;
  while (scanf("%d%d", &n, &m) == 2) {
    long long ans = 1;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0; i < m; i++) {
      int a, b;
      scanf("%d%d", &a, &b);
      if (find(a) == find(b)) {
        ans *= 2;
        ans %= MOD;
      }
      p[find(a)] = find(b);
      printf("%d\n", ((ans - 1) % MOD + MOD) % MOD);
    }
  }
  return 0;
}
