#include <bits/stdc++.h>
using namespace std;
const long long maxn = 100000 + 10;
const long long mode = 1000000000 + 9;
long long par[maxn];
long long h[maxn];
long long k;
long long getPar(long long x) {
  if (par[x] == x) return x;
  par[x] = getPar(par[x]);
  return par[x];
}
void mergeVert(long long fi, long long se) {
  if (h[fi] == h[se]) {
    h[fi]++;
    par[se] = fi;
  } else if (h[fi] > h[se])
    par[se] = fi;
  else
    par[fi] = se;
}
int main() {
  ios_base::sync_with_stdio(false);
  long long n, m;
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) par[i] = i;
  long long ans = 1;
  for (long long i = 1; i <= m; i++) {
    long long fi, se;
    cin >> fi >> se;
    if (getPar(fi) != getPar(se)) {
      mergeVert(getPar(fi), getPar(se));
    } else {
      ans *= 2;
      ans %= mode;
    }
    if (ans == 0)
      cout << mode - 1 << endl;
    else
      cout << ans - 1 << endl;
  }
}
