#include <bits/stdc++.h>
using namespace std;
long long n, m, x, y, par[100009], siz[100009], ans = 1, mod = 1e9 + 9;
long long Par(long long x) { return par[x] == x ? x : par[x] = Par(par[x]); }
void merge_(long long x, long long y) {
  x = Par(x);
  y = Par(y);
  if (siz[x] > siz[y]) swap(x, y);
  if (x == y) return;
  par[x] = y;
  siz[x]++;
}
int main() {
  scanf("%lld%lld", &n, &m);
  for (int i = 1; i <= n; i++) par[i] = i;
  while (m--) {
    scanf("%lld%lld", &x, &y);
    if (Par(x) == Par(y)) ans *= 2;
    ans %= mod;
    merge_(x, y);
    printf("%lld\n", ans - 1);
  }
  return 0;
}
