#include <bits/stdc++.h>
using namespace std;
struct DSU {
  int n, dad[100000 + 5], rnk[100000 + 5];
  void init(int nn) {
    n = nn;
    for (int i = 1; i <= n; i++) {
      rnk[i] = 0;
      dad[i] = i;
    }
  }
  int root(int v) {
    if (v == dad[v]) return v;
    return dad[v] = root(dad[v]);
  }
  void join(int v1, int v2) {
    v1 = root(v1), v2 = root(v2);
    if (v1 == v2) return;
    if (rnk[v1] < rnk[v2]) swap(v1, v2);
    dad[v2] = v1;
    if (rnk[v1] == rnk[v2]) rnk[v1]++;
  }
};
int main() {
  signed long long int ans = 1;
  int a, b, N, M;
  cin >> N >> M;
  DSU dsu;
  dsu.init(N);
  while (M--) {
    scanf("%d", &a);
    scanf("%d", &b);
    if (dsu.root(a) == dsu.root(b)) ans *= 2;
    dsu.join(a, b);
    ans %= 1000000009;
    printf("%lld\n", ans - 1);
  }
}
