#include <bits/stdc++.h>
using namespace std;
vector<int> p;
const int mod = 1000000009;
int fs(int x) { return (p[x] == x ? x : p[x] = fs(p[p[x]])); }
void un(int x, int y) {
  x = fs(x);
  y = fs(y);
  if (rand() & 1)
    p[x] = y;
  else
    p[y] = x;
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  p.resize(n);
  for (int i = 0; i < n; ++i) p[i] = i;
  int a, b, ans = 1;
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", &a, &b);
    a--;
    b--;
    if (fs(a) == fs(b)) {
      ans <<= 1;
      if (ans >= mod) ans -= mod;
    } else
      un(a, b);
    printf("%d\n", ans - 1);
  }
  return 0;
}
