#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
const double eps = 1e-8;
const int nm = 300005;
int n, k, m, t;
int res = 1;
int pa[nm];
int main() {
  int i, j, x, y, z, w;
  memset(pa, -1, sizeof(pa));
  scanf("%d%d", &n, &m);
  while (m--) {
    scanf("%d%d", &x, &y);
    while (pa[x] > 0) x = pa[x];
    while (pa[y] > 0) y = pa[y];
    if (x == y) {
      res = res * 2 % MOD;
    } else {
      if (pa[x] < pa[y])
        pa[x] += pa[y], pa[y] = x;
      else
        pa[y] += pa[x], pa[x] = y;
    }
    printf("%d\n", res - 1);
  }
  return 0;
}
