#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 28, mod = 1e9 + 9;
vector<int> g[maxn];
int a[maxn];
void add(int, int);
int k = 1;
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    a[i] = i;
    g[i].push_back(i);
  }
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    v--, u--;
    add(v, u);
    cout << k - 1 << "\n";
  }
}
void add(int v, int u) {
  if (g[a[v]].size() < g[a[u]].size()) swap(v, u);
  v = a[v], u = a[u];
  if (v == u)
    k = k * 2 % mod;
  else {
    for (auto x : g[u]) {
      a[x] = v;
      g[v].push_back(x);
    }
  }
}
