#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-10;
const double PI = acos(-1.0);
template <class T>
T gcd(T a, T b) {
  for (T c; b; c = a, a = b, b = c % b)
    ;
  return a;
}
template <class T>
void out(const vector<T> &a) {
  for (int i = 0; i < ((int)(a).size()); ++i) cout << a[i] << " ";
  cout << endl;
}
int countbit(int n) { return n == 0 ? 0 : 1 + countbit(n & (n - 1)); }
const int d8[8][2] = {{1, 0}, {-1, 0},  {0, 1},  {0, -1},
                      {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
const int d4[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
inline int dcmp(double x) { return (x > EPS) - (x < -EPS); }
inline double cross(const complex<double> &a, const complex<double> &b) {
  return (conj(a) * b).imag();
}
inline double dot(const complex<double> &a, const complex<double> &b) {
  return (conj(a) * b).real();
}
const int N = 100000;
const int MOD = 1000000000 + 9;
int f[N];
int find(int x) {
  if (f[x] != f[f[x]]) f[x] = find(f[x]);
  return f[x];
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; ++i) f[i] = i;
  int ret = 0;
  for (int i = 0; i < m; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    int rx = find(x), ry = find(y);
    if (rx != ry) {
      f[ry] = rx;
    } else {
      ret = (ret * 2 + 1) % MOD;
    }
    printf("%d\n", ret);
  }
  return 0;
}
