#include <bits/stdc++.h>
using namespace std;
long long n, m, i, j, xx, yy, ans;
long long pr[500001];
int fs(int x) {
  if (pr[x] == x)
    return x;
  else {
    pr[x] = fs(pr[x]);
    return pr[x];
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; ++i) pr[i] = i;
  long long ans = 1, x, y;
  for (i = 0; i < m; ++i) {
    scanf("%d%d", &x, &y);
    xx = fs(x);
    yy = fs(y);
    if (xx == yy) ans = (ans * 2) % 1000000009;
    cout << (ans - 1 + 1000000009) % 1000000009 << endl;
    if (xx != yy) pr[xx] = yy;
  }
}
