#include <bits/stdc++.h>
void unionInit(int d[], int s) {
  int i;
  for (i = 0; i < s; i++) d[i] = i;
}
int unionGet(int d[], int n) {
  int t = n, k;
  while (d[t] != t) t = d[t];
  while (d[n] != n) k = d[n], d[n] = t, n = k;
  return n;
}
int unionConnect(int d[], int a, int b) {
  a = unionGet(d, a);
  b = unionGet(d, b);
  if (a == b) return 0;
  d[a] = b;
  return 1;
}
int main() {
  int i, j, k, l, m, n;
  int ind[110000];
  int res;
  while (scanf("%d%d", &n, &m) == 2) {
    unionInit(ind, n);
    res = 1;
    while (m--) {
      scanf("%d%d", &i, &j);
      i--;
      j--;
      if (unionConnect(ind, i, j) == 0) res = (res * 2) % 1000000009;
      printf("%d\n", (res + 1000000009 - 1) % 1000000009);
    }
  }
  return 0;
}
