#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
const int mod = 1000000009;
int id[MAXN];
int root(int i) {
  while (i != id[i]) id[i] = id[id[i]], i = id[i];
  return i;
}
bool isCo(int i, int j) { return root(i) == root(j); }
long long ans = 0;
void U(int i, int j) {
  i = root(i);
  j = root(j);
  if (i == j) {
    ans = ans * 2 + 1;
    ans %= mod;
  } else {
    id[i] = j;
  }
}
int main() {
  int v, e;
  scanf("%d%d", &v, &e);
  for (int i = 0; i < MAXN; i++) id[i] = i;
  int a, b;
  while (e--) {
    scanf("%d%d", &a, &b);
    U(a, b);
    printf("%d\n", (int)ans);
  }
}
