#include <bits/stdc++.h>   using namespace std;   const int N = 1e5 + 5;   const int MOD = 1000000009;   int parent[N];   int Rank[N];   int Find(int x) {     if (parent[x] != x) {       parent[x] = Find(parent[x]);     }     return parent[x];   }   bool Union(int x, int y) {     x = Find(x);     y = Find(y);     if (x == y) return false;     if (Rank[x] < Rank[y]) {       parent[x] = y;     } else if (Rank[x] > Rank[y]) {       parent[y] = x;     } else {       parent[x] = y;       Rank[y]++;     }     return true;   }   int main() {     int n, m, a, b;     scanf( %d %d , &n, &m);     for (int i = 1; i <= n; i++) {       parent[i] = i;     }     int ans = 1;     while (m--) {       scanf( %d %d , &a, &b);       if (!Union(a, b)) {         ans = (ans * 2) % MOD;       }       printf( %d n , ans ? ans - 1 : MOD - 1);     }     return 0;   }   