#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:64000000")
using namespace std;
const int INF = (int)1E9;
const long long INF64 = (long long)1E18;
const long double EPS = 1E-8;
const long double PI = 3.1415926535897932384626433832795;
const int MAXN = 100100;
const int MOD = INF + 9;
int n, m, l[MAXN], deg[MAXN];
int getLeader(int v) {
  if (v != l[v]) l[v] = getLeader(l[v]);
  return l[v];
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < (int)(n); i++) l[i] = i;
  int ans = 1;
  for (int i = 0; i < (int)(m); i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    v = getLeader(v - 1);
    u = getLeader(u - 1);
    if (v != u) {
      if (rand() % 2 == 0) swap(v, u);
      l[v] = u;
    } else
      ans = (ans * 2) % MOD;
    printf("%d\n", (ans - 1 + MOD) % MOD);
  }
  return 0;
}
