#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
int N, M;
int father[100010];
int iroot(int i) {
  if (father[i] == i) return i;
  return father[i] = iroot(father[i]);
}
int main() {
  while (~scanf("%d%d", &N, &M)) {
    int ans = 0;
    for (int i = 1; i <= N; ++i) father[i] = i;
    while (M--) {
      int a, b;
      scanf("%d%d", &a, &b);
      a = iroot(a);
      b = iroot(b);
      if (a == b)
        ans = (ans * 2 + 1) % MOD;
      else
        father[a] = b;
      printf("%d\n", ans);
    }
  }
  return 0;
}
