#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const long long INF = 1e18;
int rd() { return RAND_MAX == 32767 ? ((rand() << 15) ^ rand()) : rand(); }
template <class T>
void Read_T(T &x) {
  char ch;
  while ((ch = getchar()) && (ch < '0' || ch > '9'))
    ;
  x = ch - '0';
  while ((ch = getchar()) && ch >= '0' && ch <= '9') x = x * 10 + ch - '0';
}
template <class T>
void Read_S(T &x) {
  char opt, ch = 1;
  while ((opt = ch) && (ch = getchar()) && (ch < '0' || ch > '9'))
    ;
  x = ch - '0';
  while ((ch = getchar()) && ch >= '0' && ch <= '9') x = x * 10 + ch - '0';
  if (opt == '-') x = -x;
}
const int maxn = 100010;
const int md = 1000000009;
int p[maxn];
int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); }
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) p[i] = i;
  int cnt = 1, res = 0;
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--;
    v--;
    if (Find(u) == Find(v)) {
      res = (res + cnt) % md;
      cnt = (cnt + cnt) % md;
    } else
      p[p[u]] = p[v];
    printf("%d\n", res);
  }
  return 0;
}
