#include<iostream>
#define p 1000000009
using namespace std;
int read()
{
int f=0;
char x;x=getchar();
while(x<‘0‘||x>‘9‘) x=getchar();
while(x>=‘0‘&&x<=‘9‘)
{
f=f*10+x-‘0‘;
x=getchar();
}
return f;
}
int fa[200001];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main()
{
int n,m;
int ans=1;
n=read(),m=read();
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int a,b;
a=read(),b=read();
int a1=find(a),b1=find(b);
if(a1==b1) ans*=2;
else fa[a1]=fa[b];
printf("%d\n",(ans-1)%p);
ans%=p;
}
}

2014082701黑魔法师之门（C++）