#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int mod = 1000000009;
int pnt[N], n, m;
int find(int x) {
  if (x != pnt[x]) pnt[x] = find(pnt[x]);
  return pnt[x];
}
void solve() {
  int u, v;
  for (int i = 0; i < n; ++i) pnt[i] = i;
  int ans = 1;
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &u, &v);
    u--;
    v--;
    int fu = find(u);
    int fv = find(v);
    if (fu == fv) {
      ans = ans * 2 % mod;
    } else {
      pnt[fu] = fv;
    }
    printf("%d\n", (ans + mod - 1) % mod);
  }
}
int main() {
  while (scanf("%d%d", &n, &m) != EOF) {
    solve();
  }
  return 0;
}
