#include <bits/stdc++.h>
using namespace std;
vector<int> p, st;
int get_parent(int cur) {
  while (p[cur] != cur) {
    st.push_back(cur);
    cur = p[cur];
  }
  for (int i = 0; i < st.size(); ++i) p[st[i]] = cur;
  st.clear();
  return cur;
}
void unite(int p1, int p2) {
  srand(time(0));
  if (rand() & 1)
    p[p1] = p2;
  else
    p[p2] = p1;
}
int main() {
  int n, m, a, b, count = 1, M = 1000000009;
  scanf("%d%d", &n, &m);
  p.resize(n);
  for (int i = 0; i < n; ++i) p[i] = i;
  while (m--) {
    scanf("%d%d", &a, &b);
    int p1 = get_parent(a - 1), p2 = get_parent(b - 1);
    if (p1 != p2)
      unite(p1, p2);
    else
      count = (count << 1) % M;
    printf("%d\n", (count - 1 + M) % M);
  }
  return 0;
}
