#include <bits/stdc++.h>
int d[100010], r[100010], en[100010];
int an;
void f(int x, int y) {
  while (x != d[x]) x = d[x];
  while (y != d[y]) y = d[y];
  if (x != y) {
    if (r[x] < r[y]) {
      d[x] = y;
      en[y] += en[x];
    } else if (r[x] > r[y]) {
      d[y] = x;
      en[x] += en[y];
    } else {
      d[x] = y;
      en[y] += en[x];
      r[y]++;
    }
    return;
  }
  an <<= 1;
  an %= 1000000009;
}
int main() {
  int n, m, i, x, y;
  an = 1;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) d[i] = i;
  while (m--) {
    scanf("%d%d", &x, &y);
    f(x, y);
    printf("%d\n", (an + 1000000009 - 1) % 1000000009);
  }
}
