#include <bits/stdc++.h>
using namespace std;
int fa[500010], ans = 1;
int gf(int x) {
  if (fa[x] == x) return x;
  return fa[x] = gf(fa[x]);
}
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[1000000], *p1 = buf + 1000000, *pend = buf + 1000000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 1000000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
}
struct Ostream_fwrite {
  char *buf, *p1, *pend;
  Ostream_fwrite() {
    buf = new char[1000000];
    p1 = buf;
    pend = buf + 1000000;
  }
  void out(char ch) {
    if (p1 == pend) {
      fwrite(buf, 1, 1000000, stdout);
      p1 = buf;
    }
    *p1++ = ch;
  }
  void println(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
    out('\n');
  }
  void println(char *s) {
    while (*s) out(*s++);
    out('\n');
  }
  void flush() {
    if (p1 != buf) {
      fwrite(buf, 1, p1 - buf, stdout);
      p1 = buf;
    }
  }
  ~Ostream_fwrite() { flush(); }
} Ostream;
inline void println(int x) { Ostream.println(x); }
inline void flush() { Ostream.flush(); }
};  // namespace fastIO
using namespace fastIO;
int main() {
  int n, m, x, y;
  read(n);
  read(m);
  for (int i = 1; i <= n; i++) fa[i] = i;
  for (int i = 1; i <= m; i++) {
    read(x);
    read(y);
    if (gf(x) == gf(y)) {
      ans = (ans << 1);
      if (ans >= 1000000009) ans -= 1000000009;
    } else
      fa[gf(y)] = fa[gf(x)];
    println(ans - 1);
  }
  return 0;
}
