#include <bits/stdc++.h>
using namespace std;
long long p[100002];
long long Q = 1e9 + 9;
long long find_set(long long x) {
  if (x == p[x]) {
    return x;
  }
  return p[x] = find_set(p[x]);
}
int main() {
  long long n, m;
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) {
    p[i] = i;
  }
  long long ans = 1;
  for (long long i = 0; i < m; i++) {
    long long a, b;
    cin >> a >> b;
    long long x, y;
    x = find_set(a);
    y = find_set(b);
    if (x == y) {
      ans = ans * 2;
      ans %= Q;
    } else {
      if (x > y) {
        swap(x, y);
      }
      p[y] = x;
    }
    long long pr = (ans - 1 + Q) % Q;
    cout << pr << "\n";
  }
  return 0;
}
