#include <bits/stdc++.h>
using namespace std;
int mod(int x) {
  return (x % 1000000009 >= 0 ? x % 1000000009 : x % 1000000009 + 1000000009);
}
int P[111111], R[111111];
int find(int x) { return (P[x] == x ? x : P[x] = find(P[x])); }
int main() {
  int N, M;
  cin >> N >> M;
  for (int i = 1; i <= N; i++) P[i] = i;
  int u, v;
  int ans = 1;
  while (M--) {
    scanf("%d %d", &u, &v);
    u = find(u), v = find(v);
    if (u == v)
      ans = mod(ans * 2);
    else if (R[u] < R[v])
      P[u] = v;
    else if (R[u] == R[v])
      P[u] = v, R[v]++;
    else
      P[v] = u;
    cout << mod(ans - 1) << endl;
  }
}
