#include <bits/stdc++.h>
using namespace std;
int p[111111];
int r[111111];
int findParent(int x) {
  if (x == p[x]) return x;
  return p[x] = findParent(p[x]);
}
const int MOD = 1000000009;
void unite(int a, int b) {
  a = findParent(a);
  b = findParent(b);
  if (r[a] < r[b]) {
    p[a] = b;
  } else {
    p[b] = a;
    if (r[b] == r[a]) ++r[a];
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  int ans = 1;
  for (int i = 1; i <= n; i++) p[i] = i;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    if (findParent(a) == findParent(b)) {
      ans <<= 1;
      ans %= MOD;
    } else {
      unite(a, b);
    }
    cout << ans - 1 << endl;
  }
  return 0;
}
