#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
int g[100005];
int FIND(int x) { return g[x] == x ? x : g[x] = FIND(g[x]); }
void UNION(int x, int y) { g[FIND(x)] = FIND(y); }
int main(void) {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) g[i] = i;
  int now = 1;
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (FIND(x) == FIND(y)) now = now * 2 % MOD;
    UNION(x, y);
    printf("%d\n", now - 1);
  }
  return 0;
}
