#include <bits/stdc++.h>
template <typename T>
inline void swap(T &a, T &b) {
  T c = a;
  a = b;
  b = c;
}
template <typename T>
inline const T &min(const T &a, const T &b) {
  return a < b ? a : b;
}
template <typename T>
inline const T &min(const T &a, const T &b, const T &c) {
  return min(a, min(b, c));
}
template <typename T>
inline const T &max(const T &a, const T &b) {
  return b < a ? a : b;
}
template <typename T>
inline const T &max(const T &a, const T &b, const T &c) {
  return max(a, max(b, c));
}
template <typename T>
inline T abs(const T &a) {
  return a < 0 ? -a : a;
}
template <typename T>
inline T sqr(const T &a) {
  return a * a;
}
template <typename T>
inline T lowbit(const T &a) {
  return a & -a;
}
const int tmod = 1000000009;
const int maxn = 100000 + 5;
long long pow2(int k) {
  if (k <= 60) return (1LL << k) % tmod;
  int i = 1;
  long long j = 2;
  long long ans = 1;
  for (i = 1; i <= k; i <<= 1) {
    if (k & i) ans = ans * j % tmod;
    j = j * j % tmod;
  }
  return ans;
}
int td = 0;
int father[maxn];
int tnum;
int findfather(int i) {
  return i == father[i] ? i : father[i] = findfather(father[i]);
}
int n, m;
long long ans;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) father[i] = i;
  for (int i = 1; i <= m; i++) {
    int t1, t2;
    scanf("%d%d", &t1, &t2);
    int tfa = findfather(t1);
    int tfb = findfather(t2);
    if (tfa != tfb) {
      printf("%I64d\n", ans);
      father[tfa] = tfb;
    } else {
      ans = (ans + pow2(td)) % tmod;
      printf("%I64d\n", ans);
      td++;
    }
  }
}
