#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
int n;
int m;
int par[100005];
int get(int x) { return par[x] == -1 ? x : par[x] = get(par[x]); }
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) par[i] = -1;
  long long res = 0;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    int pa = get(a);
    int pb = get(b);
    if (pa == pb) {
      res = 2LL * res + 1LL;
      res %= mod;
    } else
      par[pa] = pb;
    cout << res << endl;
  }
  return 0;
}
