#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1E-7;
const int MOD = 1000000009;
const int maxn = 100005;
int fa[maxn], n, m;
inline int getfa(int va) {
  if (fa[va] == va) return va;
  fa[va] = getfa(fa[va]);
  return fa[va];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) fa[i] = i;
  int ans = 1;
  for (; m--;) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (getfa(x) != getfa(y))
      fa[getfa(x)] = getfa(y);
    else {
      ans += ans;
      if (ans >= MOD) ans -= MOD;
    }
    printf("%d\n", (ans + MOD - 1) % MOD);
  }
  return 0;
}
