#include <bits/stdc++.h>
const int MaxN = 100111;
const int mod = 1000000009;
int f[MaxN];
int getFather(int x) {
  if (f[x] == x) return f[x];
  return f[x] = getFather(f[x]);
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) f[i] = i;
  int ans = 0;
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (getFather(x) == getFather(y))
      ans = ((ans * 2) % mod + 1) % mod;
    else
      f[getFather(y)] = getFather(x);
    printf("%d\n", ans % mod);
  }
  return 0;
}
