#include <bits/stdc++.h>
using namespace std;
int P[100001];
void CreateSet(int x) { P[x] = x; }
int FindSet(int x) {
  if (x != P[x]) P[x] = FindSet(P[x]);
  return P[x];
}
int MergeSets(int x, int y) {
  int PX = FindSet(x);
  int PY = FindSet(y);
  if (PX == PY) return 0;
  P[PX] = PY;
  return 1;
}
int main() {
  int n, m;
  int i, j, u, v;
  scanf("%d %d", &n, &m);
  for (i = 1; i <= n; i++) P[i] = i;
  int kq = 0;
  for (i = 0; i < m; i++) {
    scanf("%d %d", &u, &v);
    u = FindSet(u);
    v = FindSet(v);
    if (u == v)
      kq = (2 * kq + 1) % 1000000009;
    else
      P[u] = v;
    printf("%d\n", kq);
  }
  return 0;
}
