#include <bits/stdc++.h>
int N, M, mom[100005], ans;
inline int par(int n) { return mom[n] == n ? n : (mom[n] = par(mom[n])); }
int main() {
  int i, a, b, p, q;
  scanf("%d%d", &N, &M);
  for (i = 1; i <= N; i++) mom[i] = i;
  while (M--) {
    scanf("%d%d", &a, &b);
    p = par(a), q = par(b);
    if (p == q)
      ans = (ans + ans + 1) % 1000000009;
    else
      mom[p] = q;
    printf("%d\n", ans);
  }
}
