#include <bits/stdc++.h>
using namespace std;
const int mod = 1LL * 1000 * 1000 * 1000 + 9;
struct DSU {
  vector<int> par, size;
  int comp;
  DSU(const int &n) {
    comp = n;
    par.push_back(-1), size.push_back(-1);
    for (int i = 1; i <= n; i++) par.push_back(i), size.push_back(1);
  }
  int findRoot(int v) {
    return par[v] == par[par[v]] ? par[v] : par[v] = findRoot(par[v]);
  }
  bool Union(int v, int u) {
    int pv = findRoot(v), pu = findRoot(u);
    if (pv == pu) return true;
    if (size[pv] > size[pu]) swap(pv, pu);
    par[pv] = par[pu], size[pu] += size[pv], comp--;
    return false;
  }
  int sz(int v) { return size[findRoot(v)]; }
  bool check(int v, int u) { return findRoot(v) == findRoot(u); }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, m;
  cin >> n >> m;
  DSU G(n);
  int ans = 0;
  while (m--) {
    int v, u;
    cin >> v >> u;
    if (G.Union(v, u)) ans = (ans * 2 + 1) % mod;
    cout << ans << '\n';
  }
  return 0;
}
