#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 77, Mod = 1000000009;
int n, m, Par[N], A = 1;
int Find(int x) { return (Par[x] == 0 ? x : Par[x] = Find(Par[x])); }
inline void Merge(int v, int u) {
  v = Find(v), u = Find(u);
  if (v == u) {
    A = (A + A >= Mod) ? (A + A - Mod) : (A + A);
    return;
  }
  Par[u] = v;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int v, u, i = 1; i <= m; ++i) {
    scanf("%d %d", &v, &u);
    Merge(v, u);
    printf("%d\n", (A - 1 + Mod) % Mod);
  }
  return 0;
}
