#include <bits/stdc++.h>
const int MOD = 1e9 + 9;
const int INF = 1011111111;
const int LLINF = 1000111000111000111LL;
const long double EPS = 1e-10;
const long double PI = 3.14159265358979323;
using namespace std;
int powm(int base, int exp, int mod = MOD) {
  int ans = 1;
  while (exp) {
    if (exp & 1) ans = (ans * base) % mod;
    exp >>= 1, base = (base * base) % mod;
  }
  return ans;
}
const int N = 100005;
struct DSU {
  int sze[N], arr[N];
  void init(int n) {
    for (int i = 0; i <= n; i++) arr[i] = i, sze[i] = 1;
  }
  void get_union(int a, int b) {
    int root_a = root(a), root_b = root(b);
    if (sze[root_a] < sze[root_b])
      arr[root_a] = arr[root_b], sze[root_b] += sze[root_a];
    else
      arr[root_b] = arr[root_a], sze[root_a] += sze[root_b];
  }
  int root(int x) {
    while (arr[x] != x) arr[x] = arr[arr[x]], x = arr[x];
    return x;
  }
} dsu;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m, a, b, ret = 1;
  cin >> n >> m;
  dsu.init(n);
  while (m--) {
    cin >> a >> b;
    if (dsu.root(a) == dsu.root(b))
      ret = (ret * 2) % MOD;
    else
      dsu.get_union(a, b);
    cout << (ret - 1 + MOD) % MOD << '\n';
  }
  return 0;
}
