#include <bits/stdc++.h>
using namespace std;
long long modul = 1000000009;
int n, m, father[100005], depth[100005];
long long power(long long n, long long deg) {
  if (deg == 0)
    return 1LL;
  else {
    long long tmp = power(n, deg / 2);
    tmp = (tmp * tmp) % modul;
    if (deg % 2 == 1) tmp = (tmp * n) % modul;
    return tmp;
  }
}
int find(int u) { return (father[u] = (u == father[u]) ? u : find(father[u])); }
void merge(int u, int v) {
  int fu = find(u), fv = find(v);
  father[fu] = fv;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int u = 0; u < (n); u++) {
    father[u] = u;
    depth[u] = 1;
  }
  int pow2 = 1, u, v;
  for (int i = 0; i < (m); i++) {
    scanf("%d%d", &u, &v);
    u--;
    v--;
    if (find(u) == find(v))
      pow2 = (2 * pow2) % modul;
    else
      merge(u, v);
    cout << (pow2 - 1) << endl;
  }
  return 0;
}
