#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 * 1000 + 13;
const long long base = 1000 * 1000 * 1000 + 9;
int djs[maxn];
int get(int p) {
  if (djs[p] == p) return p;
  return djs[p] = get(djs[p]);
}
void united(int a, int b) {
  a = get(a);
  b = get(b);
  djs[a] = b;
}
int add(long long a, long long b) {
  a = (a + b + base) % base;
  return (int)a;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) djs[i] = i;
  long long res = 1;
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (get(a) == get(b)) res = (res * 2) % base;
    united(a, b);
    printf("%d\n", add(res, -1));
  }
  return 0;
}
