#include <bits/stdc++.h>
using namespace std;
int inv[112345];
const int mod = 1000000009;
inline int ff(int& x) {
  if (inv[x] == x) return x;
  return inv[x] = ff(inv[x]);
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) inv[i] = i;
  int ans = 1;
  int a, b;
  int x, y;
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &a, &b);
    x = ff(a), y = ff(b);
    if (x != y) {
      inv[x] = y;
    } else {
      ans *= 2;
      ans %= mod;
    }
    printf("%d\n", ans - 1);
  }
  return 0;
}
