#include <bits/stdc++.h>
using namespace std;
const int Maxn = 100 * 1000 + 10, Mod = 1000 * 1000 * 1000 + 9;
int n, m, par[Maxn], powe[Maxn], ans;
int findP(int v) {
  if (par[v] == v) return v;
  par[v] = findP(par[v]);
  return par[v];
}
int main() {
  scanf("%d%d", &n, &m);
  powe[0] = 1;
  for (int i = 1; i < m; i++) powe[i] = (powe[i - 1] * 2) % Mod;
  for (int i = 0; i < n; i++) par[i] = i;
  int u, v, num = n;
  ans = n;
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    u--;
    v--;
    u = findP(u), v = findP(v);
    if (u != v) {
      num--;
      par[v] = u;
    }
    printf("%d\n", (powe[i + 1 - n + num] - 1 + Mod) % Mod);
  }
  return 0;
}
