#include <bits/stdc++.h>
using namespace std;
const double pi = 2 * acos(0.0);
int n, m, t, k[100001], x, y, i;
long long uns;
int f(int v) {
  if (v == k[v])
    return v;
  else
    return k[v] = f(k[v]);
}
int main() {
  cin >> n >> m;
  for (i = 1; i <= n; i++) k[i] = i;
  uns = 1;
  for (i = 1; i <= m; i++) {
    cin >> x >> y;
    if (f(x) == f(y)) uns = (uns * 2) % 1000000009;
    k[f(x)] = f(y);
    cout << uns - 1 << endl;
  }
}
