#include <bits/stdc++.h>
using namespace std;
double PI = 3.141592653589793;
const int P = 1e9 + 9;
class mint {
 public:
  static int init_siz;
  static vector<mint> inverse, factorial;
  static int mintP;
  int n;
  static mint exp(mint a, long long e) {
    mint res = 1;
    while (e) {
      if (e & 1) res *= a;
      a *= a;
      e >>= 1;
    }
    return res;
  }
  static void init(int n) {
    init_siz = n;
    inverse.resize(n + 1);
    factorial.resize(n + 1);
    factorial[0] = 1;
    for (int i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i;
    inverse[n] = exp(factorial[n], mintP - 2);
    for (int i = n - 1; i >= 0; i--) inverse[i] = inverse[i + 1] * (i + 1);
  }
  static mint inv(mint const& a) {
    return (init_siz >= a.n ? inverse[a.n] * (a.n > 1 ? fac(a - 1) : 1)
                            : exp(a, mintP - 2));
  }
  static mint cinv(mint const& a) {
    return (init_siz >= a.n ? inverse[a.n] : exp(fac(a), mintP - 2));
  }
  static mint fac(mint const& a) {
    if (init_siz >= a.n)
      return factorial[a.n];
    else {
      mint out = 1;
      for (int i = 0; i < a.n; i++) out *= (i + 1);
      return out;
    }
  }
  mint(long long val = 0) {
    n = val % mintP;
    if (n < 0) n += mintP;
  }
  mint& operator+=(mint const& b) {
    n += b.n;
    if (n >= mintP) n -= mintP;
    return *this;
  }
  mint& operator-=(mint const& b) {
    n -= b.n;
    if (n < 0) n += mintP;
    return *this;
  }
  mint& operator*=(mint const& b) {
    n = (long long)n * b.n % mintP;
    return *this;
  }
  mint exp(long long e) { return exp(*this, e); }
  mint inv() { return inv(*this); }
  mint& operator/=(mint const& b) { return *this *= inv(b); }
  friend std::ostream& operator<<(std::ostream& os, mint const& a) {
    return os << (a.n < 0 ? a.n + mintP : a.n);
  }
  friend mint operator+(mint a, mint const b) { return a += b; }
  friend mint operator-(mint a, mint const b) { return a -= b; }
  friend mint operator-(mint const a) { return 0 - a; }
  friend mint operator*(mint a, mint const b) { return a *= b; }
  friend mint operator/(mint a, mint const b) { return a /= b; }
  friend bool operator==(mint const& a, mint const& b) { return a.n == b.n; }
  friend bool operator!=(mint const& a, mint const& b) { return a.n != b.n; }
};
int mint::init_siz = 0;
int mint::mintP = P;
vector<mint> mint::factorial, mint::inverse;
class dsu {
 private:
  int N;
  vector<int> par;
  int getpar(int v) {
    if (par[v] != v) par[v] = getpar(par[v]);
    return par[v];
  }
  pair<int, int> getparhei(int v) {
    if (par[v] == v)
      return {v, 0};
    else {
      auto temp = getparhei(par[v]);
      temp.second++;
      return temp;
    }
  }

 public:
  dsu(int siz) {
    N = siz;
    par.resize(N);
    iota(par.begin(), par.end(), 0);
  }
  int id(int v) { return getpar(v); }
  void merge(int v1, int v2) {
    auto par1 = getparhei(v1);
    auto par2 = getparhei(v2);
    if (par1.second < par2.second) swap(par1, par2);
    par[par2.first] = par1.first;
  }
  bool same(int v1, int v2) { return getpar(v1) == getpar(v2); }
};
void solve() {
  int n, m;
  cin >> n >> m;
  dsu id(n);
  int cnt = 0;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    if (id.id(u) == id.id(v))
      cnt++;
    else
      id.merge(u, v);
    cout << mint::exp(2, cnt) - 1 << '\n';
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int T = 1;
  for (int c = 1; c < T + 1; c++) {
    solve();
  }
}
