#include <bits/stdc++.h>
using namespace std;
int p[100001], w[100001];
bool combine(int x, int y) {
  while (p[x] != x) x = p[x] = p[p[x]];
  while (p[y] != y) y = p[y] = p[p[y]];
  if (x == y) return false;
  if (w[x] < w[y])
    w[p[x] = y] += w[x];
  else
    w[p[y] = x] += w[y];
  return true;
}
int main() {
  int n, m, x, y, ans = 1;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) w[p[i] = i] = 1;
  while (m--) {
    scanf("%d%d", &x, &y);
    if (!combine(x, y)) ans = ans * 2 % 1000000009;
    printf("%d\n", (ans + 1000000008) % 1000000009);
  }
}
