#include <bits/stdc++.h>
using namespace std;
int n, m;
int p[100010];
const int md = 1000000009;
int an = 1;
int sz[100010];
void make_set(int v) {
  p[v] = v;
  sz[v] = 1;
}
int find_set(int v) {
  if (p[v] == v) return v;
  return p[v] = find_set(p[v]);
}
void union_sets(int a, int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
  } else
    an = (an * 2) % md;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) make_set(i);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    union_sets(a, b);
    printf("%d\n", an - 1);
  }
  return 0;
}
