#include <bits/stdc++.h>
using namespace std;
typedef struct {
  int par, rank;
  long long ec;
} node;
node lets[100010];
void makeset(int x) {
  lets[x].par = x;
  lets[x].rank = 0;
  lets[x].ec = 1;
}
int findset(int x) {
  if (lets[x].par != x) lets[x].par = findset(lets[x].par);
  return lets[x].par;
}
void link(int x, int y) {
  if (lets[x].rank > lets[y].rank)
    lets[y].par = x;
  else {
    lets[x].par = y;
    if (lets[x].rank == lets[y].rank) lets[y].rank = lets[y].rank + 1;
  }
  return;
}
void unionset(int x, int y) {
  int tot = lets[findset(x)].ec + lets[findset(y)].ec - 1;
  link(findset(x), findset(y));
  lets[findset(x)].ec = tot;
  return;
}
int main() {
  int n, m;
  while (cin >> n >> m) {
    long long a, b, ans = 1;
    int i;
    for (i = 1; i <= n; i++) makeset(i);
    for (i = 1; i <= m; i++) {
      cin >> a >> b;
      if (findset(a) != findset(b)) {
        unionset(a, b);
        cout << ans - 1 << endl;
      } else {
        int tem = findset(a);
        ans = (ans * 2) % 1000000009;
        cout << ans - 1 << endl;
      }
    }
  }
  return 0;
}
