#include <bits/stdc++.h>
using namespace std;
long long lnk[100001], sze[100001], n, m;
long long find(long long x) {
  while (x != lnk[x]) x = lnk[x];
  return x;
}
void unite(long long x, long long y) {
  x = find(x);
  y = find(y);
  if (sze[x] < sze[y]) swap(x, y);
  lnk[y] = x;
  sze[x] += sze[y];
}
signed main() {
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= n; i++) lnk[i] = i, sze[i] = 1;
  long long ans = 1;
  while (m--) {
    long long x, y;
    scanf("%lld%lld", &x, &y);
    if (find(x) == find(y)) {
      ans = ans * 2 % 1000000009;
    } else
      unite(x, y);
    printf("%lld\n", (ans - 1 + 1000000009) % 1000000009);
  }
  return 0;
}
