#include <bits/stdc++.h>
using namespace std;
using LL = int64_t;
const int SZ = 100000 + 10;
const LL MOD = 1e9 + 9;
int g_n, g_m, pre[SZ];
void prete() {}
void input() {}
int Find(int x) {
  if (x == pre[x]) return x;
  return pre[x] = Find(pre[x]);
}
void solve() {
  for (int i = 0; i <= g_n; ++i) pre[i] = i;
  LL cnt = 1;
  for (int i = 0, u, v; i < g_m; ++i) {
    scanf(" %d %d", &u, &v);
    if (Find(u) == Find(v)) {
      cnt *= 2LL;
      cnt %= MOD;
    } else {
      pre[Find(u)] = Find(v);
    }
    cout << cnt - 1 << endl;
  }
}
int main() {
  prete();
  while (cin >> g_n >> g_m) {
    input();
    solve();
  }
  return 0;
}
