#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
int f[100009];
int Find(int x) {
  int s = x;
  while (f[x] != x) x = f[x];
  while (s != x) {
    int tmp = f[s];
    f[s] = x;
    s = tmp;
  }
  return x;
}
int Union(int a, int b) {
  int aa = Find(a), bb = Find(b);
  if (aa == bb)
    return true;
  else
    f[aa] = bb;
  return false;
}
int main() {
  int n, m, a, b;
  while (cin >> n >> m) {
    int sum = 1;
    for (int i = 1; i <= 100004; i++) f[i] = i;
    for (int i = 1; i <= m; i++) {
      scanf("%d %d", &a, &b);
      if (Union(a, b)) {
        sum *= 2;
        sum %= mod;
      }
      printf("%d\n", sum - 1);
    }
  }
  return 0;
}
