#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
long long int h[maxn];
long long int par[maxn];
int get_par(int u) { return par[u] == u ? u : par[u] = get_par(par[u]); }
void merg(int v, int u) {
  v = get_par(v);
  u = get_par(u);
  if (h[v] > h[u]) swap(v, u);
  par[v] = u;
  if (h[v] == h[u]) h[u]++;
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) par[i] = i;
  long long int ans = 0;
  while (m--) {
    int x, y;
    cin >> x >> y;
    int px = get_par(x);
    int py = get_par(y);
    if (px != py) {
      merg(x, y);
      int k = get_par(x);
    } else {
      ans = (ans * 2 + 1) % 1000000009;
    }
    cout << ans << endl;
  }
  return 0;
}
