#include <bits/stdc++.h>   using namespace std;   int N, M, P[100005], R = 1, a, b;   int findSet(int x) {     if (P[x] == x)       return x;     else       return (P[x] = findSet(P[x]));   }   void merge(int a, int b) { P[findSet(a)] = findSet(b); }   int main() {     scanf( %d%d , &N, &M);     for (int i = 1; i <= N; ++i) P[i] = i;     for (int i = 0; i < M; ++i) {       scanf( %d%d , &a, &b);       if (findSet(a) != findSet(b))         merge(a, b);       else {         R += R;         if (R >= 1000000009) R -= 1000000009;       }       if (R > 0)         printf( %d n , R - 1);       else         printf( 1000000008 n );     }   }   