#include <bits/stdc++.h>
using namespace std;
int N, M;
int dsu[100000], dsu_cnt;
void init_dsu(int N) {
  for (int i = 0; i < N; i++) dsu[i] = i;
  dsu_cnt = N;
}
int get_dsu(int v) {
  if (dsu[v] == v) return v;
  return (dsu[v] = get_dsu(dsu[v]));
}
int add_dsu(int v1, int v2) {
  v1 = get_dsu(v1);
  v2 = get_dsu(v2);
  if (v1 == v2) {
    return 1;
  }
  if (rand() & 1)
    dsu[v1] = v2;
  else
    dsu[v2] = v1;
  dsu_cnt--;
  return 2;
}
int main() {
  cin >> N >> M;
  init_dsu(N);
  int curr_res = 1;
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    curr_res = (curr_res * 2 / add_dsu(a, b)) % 1000000009;
    cout << (curr_res + 1000000008) % 1000000009 << "\n";
  }
}
