#include <bits/stdc++.h>
using namespace std;
const long long mod = (long long)1000 * 1000 * 1000 + 9;
const int maxn = 1000 * 100 + 1;
int n, m, r[maxn], parent[maxn];
long long javab = 1;
int par(int x) {
  if (x == parent[x]) return x;
  return parent[x] = par(parent[x]);
}
bool merge(int x, int y) {
  x = par(x);
  y = par(y);
  if (x == y) return true;
  if (r[x] < r[y]) swap(x, y);
  parent[y] = x;
  r[x] += r[y];
  return false;
}
int main() {
  ios::sync_with_stdio(false);
  int x, y;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    parent[i] = i;
    r[i] = 1;
  }
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    x--;
    y--;
    if (merge(x, y) == true) {
      javab *= 2;
      javab %= mod;
    }
    cout << javab - 1 << endl;
  }
  return 0;
}
