#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const int MAXN = 110000;
const int INF = MAXN * 10;
const long long mod = 1000000009LL;
int fa[MAXN];
long long sum[MAXN];
int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}
int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    long long ans(1);
    for (int i = 1; i <= n; ++i) {
      sum[i] = 1;
      fa[i] = i;
    }
    for (int i = 0; i < m; ++i) {
      int a, b;
      scanf("%d%d", &a, &b);
      a = find(a);
      b = find(b);
      if (a != b) {
        fa[a] = b;
        sum[b] += mod + sum[a] - 1;
        sum[b] %= mod;
      } else {
        ans = ans * 2 % mod;
      }
      printf("%I64d\n", (ans + mod - 1) % mod);
    }
  }
  return 0;
}
