#include <bits/stdc++.h>
const int MOD = 1000000009;
int pai[100010];
int lvl[100010];
void clean() {
  for (int i = 0; i < 100010; i++) {
    pai[i] = i;
    lvl[i] = 0;
  }
}
void uniao(int x, int y) {
  if (lvl[x] < lvl[y]) {
    pai[x] = y;
  } else {
    pai[y] = x;
    if (lvl[x] == lvl[y]) lvl[y]++;
  }
}
int acha(int x) {
  if (x == pai[x])
    return x;
  else {
    pai[x] = acha(pai[x]);
    return pai[x];
  }
}
int main() {
  int n, m, resp;
  int x, y;
  int p, q;
  scanf("%d %d", &n, &m);
  clean();
  resp = 1;
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &x, &y);
    p = acha(x);
    q = acha(y);
    if (p == q) {
      resp = (2 * resp) % MOD;
    } else {
      uniao(p, q);
    }
    printf("%d\n", resp - 1);
  }
  return 0;
}
