#include <bits/stdc++.h>
using namespace std;
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const double EPS = 1e-9;
const double PI = acos(-1.);
const long long LL_INF = 1e17 + 16;
const int INF = 1e9 + 10;
const long long MOD = 1e9 + 9;
const int MAXN = 2e5 + 5;
vector<int> g[MAXN];
int par[MAXN];
int cnt[MAXN];
long long mul[MAXN];
int get_par(int v) { return v == par[v] ? v : par[v] = get_par(par[v]); }
long long st2[MAXN];
long long pow_mod(long long a, long long st) {
  long long ans = 1ll;
  for (; st; st >>= 1) {
    if (st & 1) {
      ans = (ans * a) % MOD;
    }
    a = (a * a) % MOD;
  }
  return ans;
}
long long get_inv(long long a) { return pow_mod(a, MOD - 2); }
void solve() {
  int n, m;
  scanf("%d%d", &n, &m);
  st2[0] = 1;
  for (int i = (1); i <= (int)(n); i++) {
    st2[i] = (st2[i - 1] * 2) % MOD;
    par[i] = i;
    mul[i] = 1;
    cnt[i] = 0;
  }
  long long ans = 1ll;
  for (int i = (0); i < (int)(m); i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a = get_par(a), b = get_par(b);
    if (a == b) {
      cnt[a]++;
      mul[a] = (mul[a] * 2) % MOD;
      ans = (ans * 2) % MOD;
    } else {
      cnt[a] += cnt[b];
      mul[a] = (mul[a] * mul[b]) % MOD;
      par[b] = a;
    }
    printf("%lld\n", (ans + MOD - 1) % MOD);
  }
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
}
