#include <bits/stdc++.h>
using namespace std;
int p[100010];
int n[100010];
int e[100010];
int r[100010];
long long int pows[1000010];
long long int ipows[1000010];
int getP(int x) {
  if (p[x] != x) p[x] = getP(p[x]);
  return p[x];
}
long long int total = 1;
void mergeS(int x, int y) {
  int px = getP(x);
  int py = getP(y);
  if (px == py) {
    int pdiff = e[px] - n[px];
    e[px] += 1;
    int ndiff = e[px] - n[px];
    total = (total * ipows[pdiff + 1]) % 1000000009;
    total = (total * pows[ndiff + 1]) % 1000000009;
    return;
  } else {
    int pdiffx = e[px] - n[px];
    int pdiffy = e[py] - n[py];
    int ndiff = pdiffx + pdiffy + 1;
    total = (total * ipows[pdiffx + 1]) % 1000000009;
    total = (total * ipows[pdiffy + 1]) % 1000000009;
    total = (total * pows[ndiff + 1]) % 1000000009;
    ;
    n[px] = n[px] + n[py];
    n[py] = n[px];
    e[px] = e[px] + e[py] + 1;
    e[py] = e[px];
    if (r[x] > r[y])
      p[py] = px;
    else
      p[px] = py;
    if (r[x] == r[y]) r[y] += 1;
  }
}
int main() {
  int N, M;
  cin >> N >> M;
  pows[0] = ipows[0] = n[0] = 1;
  for (int i = 1; i < 100010; i++) {
    pows[i] = (pows[i - 1] * 2) % 1000000009;
    ipows[i] = (ipows[i - 1] * 500000005) % 1000000009;
    p[i] = i;
    n[i] = 1;
  }
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    mergeS(a, b);
    cout << (total + 1000000009 - 1) % 1000000009 << endl;
  }
  return 0;
}
