#include <bits/stdc++.h>
int MOD = 1000000009, prev[100010];
int get(int vr) { return (prev[vr] == vr ? vr : prev[vr] = get(prev[vr])); }
int main() {
  int i, n, m, x, y, BR = 1;
  scanf("%d%d", &n, &m);
  for (i = 0; i <= n; ++i) prev[i] = i;
  while (m-- > 0) {
    scanf("%d%d", &x, &y);
    if (get(x) == get(y))
      BR = (BR << 1) % MOD;
    else
      prev[get(x)] = get(y);
    printf("%d\n", (BR - 1 + MOD) % MOD);
  }
  return 0;
}
