#include <bits/stdc++.h>
const long double PI = acos(-1);
const long double eps = 0.0000000001;
const long long INF = 0x3fffffffffffffff;
const long long MOD = 1000000009;
long long n, m, fa[100005], ans = 1;
long long find(long long now) {
  return fa[now] == now ? now : fa[now] = find(fa[now]);
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin >> n >> m;
  for (long long i = 1; i <= n; ++i) fa[i] = i;
  for (long long i = 1; i <= m; ++i) {
    static long long a, b;
    std::cin >> a >> b;
    if (find(a) != find(b))
      fa[find(a)] = find(b);
    else
      ans = (ans + ans) % MOD;
    std::cout << (ans - 1) << std::endl;
  }
  return 0;
}
