#include <bits/stdc++.h>
using namespace std;
int testnum;
const int maxn = 100005;
int par[maxn];
int size[maxn];
int find(int u) {
  if (par[u] == u) return u;
  return par[u] = find(par[u]);
}
bool unify(int u, int v) {
  int cu = find(u), cv = find(v);
  if (cu == cv) return true;
  if (size[cu] > size[cv]) {
    par[cv] = cu;
    size[cu] += size[cv];
  } else {
    par[cu] = cv;
    size[cv] += size[cu];
  }
  return false;
}
int n, m;
void preprocess() {
  for (int i = 0; i < maxn; i++) {
    par[i] = i;
    size[i] = 1;
  }
}
long long mod = 1000000009;
void solve() {
  int a, b;
  long long ans = 1;
  for (int i = 0; i < m; i++) {
    scanf("%d", &a);
    scanf("%d", &b);
    bool z = unify(a, b);
    if (z) {
      ans = (ans + ans) % mod;
    }
    cout << (ans - 1) << endl;
  }
}
bool input() {
  scanf("%d", &n);
  scanf("%d", &m);
  return true;
}
int main() {
  preprocess();
  int T = 1;
  for (testnum = 1; testnum <= T; testnum++) {
    if (!input()) break;
    solve();
  }
}
