#include <bits/stdc++.h>
const long long LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 100000 + 10;
const int MOD = 1000000009;
int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
using namespace std;
int n, m;
int pre[MAXN];
void init(int n) {
  for (int i = 0; i <= n; i++) pre[i] = i;
}
int find(int x) { return pre[x] != x ? pre[x] = find(pre[x]) : x; }
int main() {
  cin >> n >> m;
  init(n);
  int ans = 1;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    if (find(x) == find(y))
      ans = ans * 2 % MOD;
    else
      pre[find(x)] = find(y);
    printf("%d\n", ans - 1);
  }
  return 0;
}
