#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 9;
int n, m;
int fa[100005];
int Find(int x) {
  int r = x, y;
  while (x != fa[x]) x = fa[x];
  while (r != x) {
    y = fa[r];
    fa[r] = x;
    r = y;
  }
  return x;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin >> n >> m;
  int x, y, xx, yy;
  long long ans = 1;
  for (int i = 0; i <= n; i++) fa[i] = i;
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    xx = Find(x), yy = Find(y);
    if (xx == yy) {
      ans = (ans + ans) % MOD;
    } else
      fa[xx] = yy;
    cout << ans - 1 << endl;
  }
}
