#include <bits/stdc++.h>
using namespace std;
long long in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
const long long maxn = 1e5 + 10;
const long long mod = 1e9 + 9;
long long id[maxn], pr[maxn];
inline long long root(long long x) {
  return pr[x] == x ? x : pr[x] = root(pr[x]);
}
inline bool merge(long long v, long long u) {
  v = root(v), u = root(u);
  if (v == u) return false;
  pr[v] = u;
  return true;
}
int32_t main() {
  long long n = in(), m = in();
  for (long long i = 0; i <= n; i++) pr[i] = i;
  long long res = 1;
  for (long long i = 0; i < m; i++) {
    long long v = in() - 1, u = in() - 1;
    if (merge(v, u) == 0) res = 2 * res % mod;
    cout << (res - 1 + mod) % mod << "\n";
  }
}
