#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 9;
int p[N];
int getpar(int u) {
  if (p[p[u]] == p[u]) return p[u];
  return p[u] = getpar(p[u]);
}
bool unite(int a, int b) {
  a = getpar(a);
  b = getpar(b);
  if (a == b) return false;
  p[a] = b;
  return true;
}
int main() {
  iota(p, p + N, 0);
  int n, m;
  cin >> n >> m;
  long long ans = 1;
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (!unite(a, b)) ans = (ans * 2) % MOD;
    printf("%d\n", ans - 1);
  }
}
