#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
const int Mod = 1000000009;
int n, m;
int F[N];
int GF(int x) { return F[x] == x ? x : F[x] = GF(F[x]); }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) F[i] = i;
  int ans = 1;
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--;
    y--;
    if (GF(x) != GF(y))
      F[F[x]] = F[y];
    else
      ans = ans * 2 % Mod;
    printf("%d\n", (ans - 1 + Mod) % Mod);
  }
}
