#include <bits/stdc++.h>
using namespace std;
long long int modulo = 1e9 + 9;
int n, m;
int pare[1000000];
int identificador(int u) {
  if (pare[u] == 0) return u;
  int idpareu = identificador(pare[u]);
  pare[u] = idpareu;
  return idpareu;
}
int main() {
  cin >> n >> m;
  long long int sol = 1;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    int idu = identificador(u);
    int idv = identificador(v);
    if (idu == idv)
      sol = (2 * sol) % modulo;
    else
      pare[idu] = idv;
    cout << (sol + modulo - 1) % modulo << endl;
  }
}
