#include <bits/stdc++.h>
using namespace std;
void error2(const string &s, const int &t) {
  cerr << endl << "  " << s << " = " << t << endl;
}
const int MAXINT = 2147483647, MAXSINT = 32767, N = 1000ll * 1000 * 1000ll + 9;
int cl[1000 * 300], ncl;
int ff(int a) {
  if (cl[a] - a) {
    int tmp = cl[a];
    cl[a] = ff(tmp);
    return cl[a];
  } else
    return a;
}
int main() {
  ios::sync_with_stdio(false);
  int n, m, t, tt, tmp = 0;
  long long ans = 1;
  char c;
  cin >> n >> m;
  ncl = n;
  for (register int i = (1); i < (int)(n + 1); ++i) cl[i] = i;
  for (register int i = (0); i < (int)(m); ++i) {
    cin >> t >> tt;
    tmp = ncl;
    if (ff(cl[t]) - ff(cl[tt])) {
      ncl--;
      cl[ff(cl[t])] = ff(cl[tt]);
    }
    if (tmp == ncl) ans *= 2;
    ans %= N;
    cout << ans - 1 << endl;
  }
  return 0;
}
