#include <bits/stdc++.h>
#pragma comment(linker, "/stack:64000000")
using namespace std;
struct DSU {
  vector<int> rank;
  vector<int> prev;
  DSU(int n) {
    rank.assign(n, 0);
    prev.assign(n, -1);
  }
  int findSet(int x) {
    if (prev[x] == -1) return x;
    return prev[x] = findSet(prev[x]);
  }
  void unionSet(int x, int y) {
    x = findSet(x);
    y = findSet(y);
    if (x != y) {
      if (rank[x] < rank[y]) {
        prev[x] = y;
      } else {
        prev[y] = x;
        rank[x] = max(rank[x], rank[y] + 1);
      }
    }
  }
};
int main() {
  int n, m, a, b, r = 1, mod = (int)1e9 + 9, k = 0;
  scanf("%d %d", &n, &m);
  DSU d(n);
  for (int(i) = 0; (i) < (m); (i)++) {
    scanf("%d %d", &a, &b);
    --a, --b;
    if (d.findSet(a) == d.findSet(b)) {
      r *= 2;
      r %= mod;
    } else {
      d.unionSet(a, b);
    }
    printf("%d\n", (r + mod - 1) % mod);
  }
  return 0;
}
