#include <bits/stdc++.h>
using namespace std;
int parent[100000 + 1];
int Findset(int p) {
  if (parent[p] == p)
    return p;
  else {
    parent[p] = Findset(parent[p]);
    return parent[p];
  }
}
void Union(int a, int b) { parent[Findset(b)] = Findset(a); }
int main() {
  int n, m, a, b, res = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) parent[i] = i;
  for (int i = 1; i <= m; i++) {
    cin >> a >> b;
    if (Findset(a) != Findset(b))
      Union(a, b);
    else
      res = (2 * res + 1) % 1000000009;
    cout << res << endl;
  }
  return 0;
}
