#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int mmod = 1000000009;
long long z[maxn];
int se[maxn];
int nump[maxn];
int nume[maxn];
int n, m;
int find(int a) {
  if (a != se[a]) {
    return se[a] = find(se[a]);
  }
  return a;
}
void cb(int a, int b) {
  int aa = find(a);
  int bb = find(b);
  if (aa != bb) {
    se[bb] = se[aa];
    nump[aa] += nump[bb];
    nump[bb] = 0;
    nume[aa] += nume[bb];
    nume[bb] = 0;
  }
}
int main() {
  z[1] = 1;
  for (int i = 2; i < maxn; i++) z[i] = (z[i - 1] * 2 + 1) % mmod;
  memset(nume, 0, sizeof(nume));
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    se[i] = i;
    nump[i] = 1;
  }
  long long ans = 0;
  int a, b, aa, bb;
  int jj = 0;
  for (int i = 1; i <= m; i++) {
    cin >> a >> b;
    aa = find(a);
    bb = find(b);
    if (aa == bb) {
      nume[aa]++;
      jj++;
      ans = z[jj];
    } else {
      cb(aa, bb);
      nume[aa]++;
    }
    cout << ans << endl;
  }
  return 0;
}
