#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
int N, M;
long long MOD = 1000000009;
int par[200000];
int h[200000];
long long res;
void init() {
  for (int i = (0); i < (N); ++i) {
    par[i] = i;
    h[i] = 0;
  }
  res = 1;
}
int Find(int x) {
  if (x != par[x]) par[x] = Find(par[x]);
  return par[x];
}
bool Union(int x, int y) {
  if ((x = Find(x)) == (y = Find(y))) {
    res = (2 * res) % MOD;
    return false;
  }
  if (h[x] > h[y]) {
    par[y] = x;
  } else {
    par[x] = y;
    if (h[x] == h[y]) h[y]++;
  }
  return true;
}
int main() {
  cin >> N >> M;
  init();
  for (int i = (0); i < (M); ++i) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    Union(a, b);
    cout << res - 1 << endl;
  }
  return 0;
}
