描述 Description
输入格式 InputFormat
输出格式 OutputFormat
样例输入 SampleInput
4 8
3 1
3 2
2 1
2 1
1 3
1 4
2 4
2 3
样例输出 SampleOutput
0
0
1
3
7
7
15
31
数据范围和注释 Hint
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #define mod 1000000009 #define ll long long using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m; int fa[200005]; ll ans; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} int main() { n=read(),m=read(); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { int p=find(read()),q=find(read()); if(p!=q)fa[p]=q; else ans=ans*2+1; ans%=mod; printf("%lld\n",ans); } return 0; }