#include <bits/stdc++.h>
using namespace std;
int f[100005], p[100005];
int find(int a) {
  if (a == f[a]) return a;
  return f[a] = find(f[a]);
}
int main() {
  int n, m, i, a, b;
  p[0] = 1;
  for (i = 1; i < 100005 - 1; i++) p[i] = (p[i - 1] * 2) % 1000000009;
  while (~scanf("%d%d", &n, &m)) {
    for (i = 1; i <= n; i++) f[i] = i;
    int k = 0;
    while (m--) {
      scanf("%d%d", &a, &b);
      a = find(a), b = find(b);
      if (a == b)
        k++;
      else
        f[a] = b;
      printf("%d\n", p[k] - 1);
    }
  }
  return 0;
}
