#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const int MAX = 1e5 + 9, MOD = 1e9 + 9;
int f[MAX], ans = 1;
int root(int v) { return f[v] < 0 ? v : f[v] = root(f[v]); }
bool merge(int v, int u) {
  if ((v = root(v)) == (u = root(u))) return false;
  return f[u] = v, true;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0),
      memset(f, -1, sizeof f);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int v, u;
    cin >> v >> u, v--, u--;
    if (!merge(v, u)) ans = ans * 2LL % MOD;
    cout << (ans + MOD - 1) % MOD << '\n';
  }
  return 0;
}
