#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5 + 10;
const long long Mod = 1e9 + 9;
long long head[MAXN];
long long comp = 0, res = 1;
void update(long long v) {
  if (head[head[v]] != head[head[head[v]]]) {
    update(head[v]);
  }
  head[v] = head[head[v]];
}
void dsu(long long v, long long u) {
  update(v);
  update(u);
  if (head[v] == head[u]) {
    res *= 2;
    res %= Mod;
    return;
  }
  head[head[v]] = head[u];
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  comp = n;
  for (long long i = 1; i <= n; i++) {
    head[i] = i;
  }
  for (long long i = 0; i < m; i++) {
    long long v, u;
    cin >> v >> u;
    dsu(v, u);
    cout << (res + Mod - 1) % Mod << endl;
  }
}
