#include <bits/stdc++.h>
using namespace std;
int n, m;
int md = 1000000009;
int v[100000];
int findSet(int i) {
  int& x = v[i];
  if (x != i) x = findSet(x);
  return x;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) v[i] = i;
  int ret = 1;
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--, b--;
    int sa = findSet(a);
    int sb = findSet(b);
    if (sa != sb) {
      if (rand() % 2)
        v[sa] = sb;
      else
        v[sb] = sa;
    } else
      ret = (ret * 2) % md;
    printf("%d\n", ret - 1);
  }
  return 0;
}
