#include <bits/stdc++.h>
int uf[100100];
int find(int a) { return uf[a] = ((a == uf[a]) ? a : find(uf[a])); }
void join(int a, int b) { uf[find(a)] = uf[find(b)]; }
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) uf[i] = i;
  int res = 1;
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (find(a) == find(b)) res = (res * 2) % 1000000009;
    printf("%d\n", res - 1);
    join(a, b);
  }
}
