#include <bits/stdc++.h>
using namespace std;
const int md = (1e+9) + 9;
const int MAXN = 100024;
int n, m;
int p[MAXN];
int GetRoot(int s) {
  int z, x, c;
  for (z = s; z != p[z]; z = p[z])
    ;
  for (x = s; x != z; x = c) {
    c = p[x];
    p[x] = z;
  }
  return z;
}
int Work() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) p[i] = i;
  int tot = 1;
  for (int i = 0, a, b, ra, rb; i < m; i++) {
    cin >> a >> b;
    ra = GetRoot(a);
    rb = GetRoot(b);
    if (ra == rb)
      tot = (tot * 2) % md;
    else
      p[rb] = ra;
    cout << (tot + md - 1) % md << endl;
  }
  return 0;
}
int main() {
  Work();
  return 0;
}
