#include <bits/stdc++.h>
int pr[100002];
int lv[100002];
int st[100002], head;
int P(int x) {
  head = 0;
  while (pr[x] != -1) {
    st[head++] = x;
    x = pr[x];
  }
  while (head > 0) {
    pr[st[--head]] = x;
  }
  return x;
}
void Union(int x, int y) {
  x = P(x);
  y = P(y);
  if (x == y) return;
  if (lv[x] > lv[y]) {
    int t = x;
    x = y;
    y = t;
  }
  pr[x] = y;
  if (lv[x] == lv[y]) {
    lv[y]++;
  }
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  int a, b;
  int i;
  int sol = 1;
  for (i = 0; i < n; i++) {
    pr[i] = -1;
    lv[i] = 0;
  }
  for (i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    a--;
    b--;
    if (P(a) != P(b)) {
      Union(a, b);
    } else
      sol = (sol * 2) % 1000000009;
    int pr;
    pr = (sol - 1 + 1000000009) % 1000000009;
    printf("%d\n", pr);
  }
  return 0;
}
