#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:134217728")
using namespace std;
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
int n;
int m;
long long st[100500];
int mod = 1000000009;
int root[100500];
int get_root(int x) {
  if (x == root[x]) return x;
  return root[x] = get_root(root[x]);
}
void merge(int a, int b) {
  a = get_root(a);
  b = get_root(b);
  if (rand() % 2)
    root[a] = b;
  else
    root[b] = a;
}
int main() {
  cin >> n >> m;
  st[0] = 1;
  for (int i = 1; i <= m; i++) st[i] = st[i - 1] * 2 % mod;
  int p = 0;
  for (int i = 0; i < (n); i++) root[i] = i;
  for (int i = 0; i < (m); i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    if (get_root(a) == get_root(b))
      p++;
    else
      merge(a, b);
    cout << (mod - 1 + st[p]) % mod << endl;
  }
  return 0;
}
