#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
int n, m;
int p[200005];
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void Union(int a, int b) { p[find(a)] = p[find(b)]; }
int main() {
  scanf("%d%d", &n, &m);
  int ret = 1;
  for (int i = 1; i <= n; i++) p[i] = i;
  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (find(a) == find(b)) ret = ret * 2 % mod;
    Union(a, b);
    printf("%d\n", ret - 1);
  }
  return 0;
}
