#include <bits/stdc++.h>
using namespace std;
const int module = 1000000009;
int dsu[110000], answer = 1, n, m, a, b;
int get(int x) { return x == dsu[x] ? x : dsu[x] = get(dsu[x]); }
void unite(int x, int y) {
  x = get(x), y = get(y);
  if (rand() & 1) swap(x, y);
  dsu[x] = y;
}
int main() {
  srand(time(0));
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) dsu[i] = i;
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    if (get(a) == get(b)) answer *= 2, answer %= module;
    unite(a, b);
    printf("%d\n", ((answer - 1) + module) % module);
  }
  return 0;
}
