#include <bits/stdc++.h>
using std::bitset;
using std::cerr;
using std::cin;
using std::cout;
using std::deque;
using std::endl;
using std::fixed;
using std::ios_base;
using std::make_pair;
using std::make_tuple;
using std::map;
using std::nth_element;
using std::pair;
using std::queue;
using std::reverse;
using std::set;
using std::sort;
using std::stack;
using std::string;
using std::tuple;
using std::unordered_map;
using std::unordered_set;
using std::vector;
const int N = 1e5 + 5;
const int M = 1e9 + 9;
int n, m;
int p[N];
int getp(int v) { return p[v] = p[v] == v ? v : getp(p[v]); }
bool add(int v, int u) {
  v = getp(v), u = getp(u);
  if (v == u) return false;
  p[v] = u;
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  int ans = 1;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) p[i] = i;
  for (int i = 0; i < m; ++i) {
    int v, u;
    cin >> v >> u;
    if (!add(--v, --u)) ans = (ans * 2) % M;
    cout << ans - 1 << '\n';
  }
  return 0;
}
