#include <bits/stdc++.h>
using namespace std;
vector<int> V;
void initSet(int _size) {
  V.resize(_size);
  for (int i = int(0); i <= int(_size - 1); i++) V[i] = i;
}
int findSet(int i) { return (V[i] == i) ? i : (V[i] = findSet(V[i])); }
void unionSet(int i, int j) { V[findSet(i)] = findSet(j); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
long long a, b, s, N, M, A, B, r[123450];
int find(int node) {
  if (r[node]) return r[node] = find(r[node]);
  return node;
}
int main() {
  int N = 0;
  cin >> N >> M;
  s = 1;
  for (int i = 1; i <= M; ++i) {
    cin >> a >> b;
    A = find(a);
    B = find(b);
    if (A == B) {
      s = s * 2 % 1000000009;
    } else {
      r[B] = A;
    }
    if (s > 0)
      cout << s - 1 << endl;
    else
      cout << 1000000009 - 1 << endl;
  }
  return 0;
}
