#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
const int N = 100001;
int pot[N];
int p[N];
int r[N];
int ile[N];
int kr[N];
map<int, int> edge[N];
int n, m;
void make(int v) {
  p[v] = v;
  r[v] = 0;
}
int find(int v) {
  if (v != p[v]) p[v] = find(p[v]);
  return p[v];
}
bool Uunion(int u, int v) {
  int x = find(u), y = find(v);
  if (x != y) {
    if (r[x] > r[y]) {
      p[y] = x;
      kr[x] += kr[y];
    } else {
      p[x] = y;
      if (r[x] == r[y]) r[y]++;
      kr[y] += kr[x];
    }
    return true;
  } else
    return false;
}
int main() {
  scanf("%d %d", &n, &m);
  long long sum = 1;
  for (int i = 1; i <= (n); ++i) make(i);
  for (int i = 0; i < (m); ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (!Uunion(a, b)) {
      sum = (2 * sum) % MOD;
    }
    printf("%lld\n", sum - 1);
  }
}
