#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 9;
int p[100002], base[100002];
int root(int a) { return p[a] == a ? a : (p[a] = root(p[a])); }
long long ans = 1;
long long pow2(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b % 2 == 1) ans = ans * a % mod;
    a = a * a % mod;
    b /= 2;
  }
  return ans;
}
void merge(int a, int b) {
  a = root(a), b = root(b);
  if (a != b) {
    ans = ans * pow2(base[a], mod - 2) % mod;
    ans = ans * pow2(base[b], mod - 2) % mod;
    base[b] = base[b] * 1ll * base[a] % mod;
    p[a] = b;
    ans = ans * base[b] % mod;
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    p[i] = i;
    base[i] = 1;
  }
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (root(a) == root(b)) {
      ans = ans * pow2(base[root(a)], mod - 2) % mod;
      base[root(a)] = base[root(a)] * 2 % mod;
      ans = ans * base[root(a)] % mod;
    } else
      merge(a, b);
    printf("%lld\n", (ans - 1 + mod) % mod);
  }
}
