#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000009;
long long A[200000];
long long root(long long a) {
  long long i = a;
  if (A[i] != i) {
    A[i] = root(A[i]);
  }
  return A[a];
}
void unio(long long a, long long b) {
  long long ra = root(a);
  long long rb = root(b);
  if (ra != rb) {
    A[ra] = rb;
  }
}
signed main() {
  long long n, m;
  cin >> n >> m;
  long long val = 1;
  for (long long i = 1; i <= n; i++) {
    A[i] = i;
  }
  for (long long i = 1; i <= m; i++) {
    long long a, b;
    cin >> a >> b;
    if (root(a) == root(b)) {
      val = (val * 2LL) % mod;
    } else {
      unio(a, b);
    }
    val--;
    val = (val + mod) % mod;
    cout << val << endl;
    val++;
  }
}
