#include <bits/stdc++.h>
using namespace std;
int mod = 1000000009, f[int(1e6)];
int F(int x) { return f[x] != x ? f[x] = F(f[x]) : x; }
int main() {
  int n, m, x, y, res = 1, i;
  cin >> n >> m;
  for (i = 1; i <= n; i++) f[i] = i;
  for (i = 0; i < m; i++) {
    cin >> x >> y;
    if (F(x) == F(y))
      res = (res * 2LL) % mod;
    else
      f[F(x)] = F(y);
    cout << res - 1 << endl;
  }
  return 0;
}
