#include <bits/stdc++.h>
const double Pi = acos(-1.0);
using namespace std;
const int maxN = 100005;
const long long mod = 1000000009;
int n, m;
int par[maxN];
int findpar(int x) {
  if (par[x] != x) par[x] = findpar(par[x]);
  return par[x];
}
int main(int argc, char** argv) {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) par[i] = i;
  long long ans = 1;
  int a, b;
  while (m--) {
    scanf("%d %d", &a, &b);
    int pa = findpar(a), pb = findpar(b);
    if (pa == pb)
      ans = (ans * 2) % mod;
    else
      par[pb] = pa;
    printf("%lld\n", ans - 1);
  }
  return 0;
}
