#include <bits/stdc++.h>
using namespace std;
long long pwr(long long base, long long p, long long mod = (1000000009LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int n, sz[100005], par[100005];
int root(int v) {
  if (v == par[v]) return v;
  return par[v] = root(par[v]);
}
void unite(int a, int b) {
  a = root(a), b = root(b);
  if (a == b) return;
  if (sz[a] < sz[b]) swap(a, b);
  par[b] = a;
  sz[a] += sz[b];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int e;
  cin >> n >> e;
  for (int i = 1; i <= n; i++) {
    sz[i] = 1;
    par[i] = i;
  }
  long long ans = 1;
  while (e--) {
    int a, b;
    cin >> a >> b;
    if (root(a) == root(b))
      ans = (ans * 2) % (1000000009LL);
    else
      unite(a, b);
    cout << (ans - 1 + (1000000009LL)) % (1000000009LL) << endl;
  }
  return 0;
}
