#include <bits/stdc++.h>
using namespace std;
int p[100010];
int find(int a) { return p[a] == a ? a : (p[a] = find(p[a])); }
bool uni(int a, int b) {
  a = find(a), b = find(b);
  if (a == b) return false;
  p[a] = b;
  return true;
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < (int)n; i++) p[i] = i;
  int ans = 1;
  for (int i = 0; i < (int)m; i++) {
    int a, b;
    cin >> a >> b;
    if (!uni(a, b)) ans = ans * 2 % 1000000009;
    cout << (ans - 1 + 1000000009) % 1000000009 << endl;
  }
  return 0;
}
