#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e+5 + 10, mod = 1e9 + 9;
int par[maxn], P[maxn];
inline int find_par(int x) {
  if (par[x] < 0) return x;
  return par[x] = find_par(par[x]);
}
inline void merg(int x, int y) {
  if (par[x] > par[y]) swap(x, y);
  par[x] += par[y];
  par[y] = x;
}
int main() {
  P[0] = 1;
  for (int i = 1; i < maxn; par[i] = -1, i++) P[i] = (P[i - 1] * 2) % mod;
  int n, m;
  cin >> n >> m;
  int cnt = n;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    x = find_par(x), y = find_par(y);
    if (x != y) {
      cnt--;
      merg(x, y);
    }
    cout << P[i - n + cnt] - 1 << "\n";
  }
  return 0;
}
