#include <bits/stdc++.h>
using namespace std;
int n, pre[100050];
int find(int u) {
  if (pre[u] ^ u) pre[u] = find(pre[u]);
  return pre[u];
}
int main() {
  int m, u, v, ans;
  while (cin >> n >> m) {
    for (int i = 1; i <= n; i++) pre[i] = i;
    ans = 1;
    while (m--) {
      scanf("%d%d", &u, &v);
      if (find(v) != find(u))
        pre[find(v)] = find(u);
      else
        ans = ans * 2 % 1000000009;
      printf("%d\n", (ans + 1000000009 - 1) % 1000000009);
    }
  }
  return 0;
}
