#include <bits/stdc++.h>
using namespace std;
int num[100001];
int f(int k) {
  if (num[k] == k) return k;
  return num[k] = f(num[k]);
}
int main() {
  int m, n, i, a, b, ans = 0;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; ++i) num[i] = i;
  while (m--) {
    scanf("%d%d", &a, &b);
    a = f(a);
    b = f(b);
    if (a == b)
      ans = (ans * 2 + 1) % 1000000009;
    else
      num[b] = a;
    printf("%d\n", ans);
  }
  return 0;
}
