#include <bits/stdc++.h>
using namespace std;
int N, M, P[100005], R = 1, a, b;
int findSet(int x) {
  if (P[x] == x)
    return x;
  else
    return (P[x] = findSet(P[x]));
}
void merge(int a, int b) { P[findSet(a)] = findSet(b); }
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; ++i) P[i] = i;
  for (int i = 0; i < M; ++i) {
    scanf("%d%d", &a, &b);
    if (findSet(a) != findSet(b))
      merge(a, b);
    else {
      R += R;
      if (R >= 1000000009) R -= 1000000009;
    }
    if (R > 0)
      printf("%d\n", R - 1);
    else
      printf("1000000008\n");
  }
}
