#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, maxn = 100005;
int fa[maxn];
int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}
int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    for (int i = 1; i <= n; i++) fa[i] = i;
    int ans = 0;
    while (m--) {
      int a, b;
      scanf("%d%d", &a, &b);
      a = find(a), b = find(b);
      if (a == b)
        ans = (ans * 2 + 1) % 1000000009;
      else
        fa[a] = b;
      printf("%d\n", ans);
    }
  }
  return 0;
}
