#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
const int inf = 0x3f3f3f3f;
const string debug_line = "yolo";
int parent1[100010];
int child1[100010];
long long cycles[1000010];
int parent(int u) {
  while (parent1[u] != u) {
    u = parent1[u];
  }
  return u;
}
void union1(int first, int second) {
  int x1 = parent(first);
  int y1 = parent(second);
  if (x1 == y1) {
    return;
  } else {
    if (child1[x1] > child1[y1]) {
      child1[x1] += child1[y1];
      parent1[y1] = parent1[x1];
      cycles[x1] = (cycles[x1] + cycles[y1]) % 1000000009;
    } else {
      child1[y1] += child1[x1];
      parent1[x1] = parent1[y1];
      cycles[y1] = (cycles[y1] + cycles[x1]) % 1000000009;
    }
    return;
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  long long answer1 = 1;
  for (int(i) = (1); (i) < (n + 1); ++(i)) {
    parent1[i] = i;
    child1[i] = 1;
  }
  for (int(i) = (1); (i) < (m + 1); ++(i)) {
    int a, b;
    scanf("%d%d", &a, &b);
    int a1 = parent(a);
    int b1 = parent(b);
    if (a1 == b1) {
      answer1 = (2 * answer1) % 1000000009;
    } else {
      union1(a, b);
    }
    printf("%lld\n", ((answer1 - 1) % 1000000009 + 1000000009) % 1000000009);
  }
  return 0;
}
