#include <bits/stdc++.h>
using namespace std;
const int mN = 1e5 + 100, mod = 1e9 + 9;
int p[mN], n, m;
int findSet(int i) { return i == p[i] ? i : p[i] = findSet(p[i]); }
int main() {
  scanf("%d", &n), scanf("%d", &m);
  for (int i = 0; i < n; ++i) p[i] = i;
  int ans = 0;
  for (int i = 0; i < m; ++i) {
    int u, v;
    scanf("%d", &u), scanf("%d", &v);
    if (findSet(u) == findSet(v)) {
      ans = (ans << 1) | 1;
      if (ans >= mod) ans -= mod;
    } else
      p[p[u]] = p[v];
    printf("%d\n", ans);
  }
}
