#include <bits/stdc++.h>
using namespace std;
void read_file(bool outToFile = true) {}
int n, m;
int rep[100000 + 9];
void init() {
  for (int i = 0; i < n; i++) rep[i] = i;
}
int find_rep(int i) {
  if (i == rep[i])
    return i;
  else
    return rep[i] = find_rep(rep[i]);
}
bool join(int i, int j) {
  i = find_rep(i);
  j = find_rep(j);
  if (i == j) return false;
  rep[j] = i;
  return true;
}
int main() {
  read_file();
  while (scanf("%d%d", &n, &m) != EOF) {
    init();
    int ans = 1;
    for (int itr = 0; itr < m; itr++) {
      int u, v;
      scanf("%d%d", &u, &v);
      u--, v--;
      if (!join(u, v)) ans = ans + ans, ans %= (1000000009);
      printf("%d\n", ans - 1);
    }
  }
}
