#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5 + 10;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 9;
int H[maxn], par[maxn];
int find(int p) {
  if (par[p] == p) return p;
  int u = find(par[p]);
  par[p] = u;
  return u;
}
void un(int p1, int p2) {
  int par1 = find(p1), par2 = find(p2);
  if (H[par1] > H[par2]) {
    par[par2] = par1;
  } else if (H[par1] < H[par2]) {
    par[par1] = par2;
  } else {
    par[par2] = par1;
    H[par1]++;
  }
}
long long pw(long long x, long long exp1) {
  if (exp1 == 0) return 1;
  long long y = pw(x, exp1 / 2);
  y = (y * y) % MOD;
  if (exp1 & 1) y = (y * x) % MOD;
  return y;
}
inline void solve(void) {
  for (int i = (0); i < (maxn); i++) par[i] = i;
  int n, m;
  scanf("%d", &n);
  scanf("%d", &m);
  int ans = 1;
  for (int i = (0); i < (m); i++) {
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    if (find(x) != find(y)) {
      un(x, y);
      printf("%d\n", (ans - 1 + MOD) % MOD);
    } else {
      ans = (ans * 2) % MOD;
      printf("%d\n", (ans - 1 + MOD) % MOD);
    }
  }
}
int main(int argc, const char* argv[]) {
  solve();
  return 0;
}
