记录编号	586616	评测结果	AAAAAAAAAA
题目名称	[Nescafé 17] 黑魔法师之门	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.844 s
提交时间	2024-02-18 22:58:18	内存使用	10.36 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5+10,mod = 1e9+9;
int n,m;
ll ans;
struct uni{
	int fa[N];
	void init(){
		for(int i = 1;i <= n;i++)fa[i] = i;
	}
	int find(int x){
		if(x == fa[x])return x;
		return fa[x] = find(fa[x]);
	}
}U;
int main(){
	freopen("magiciana.in","r",stdin);
	freopen("magiciana.out","w",stdout);
	scanf("%d%d",&n,&m);
	U.init();
	for(int i = 1;i <= m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		x = U.find(x),y = U.find(y);
		if(x == y)ans = (ans * 2 + 1) % mod; 
		else U.fa[y] = x;
		printf("%lld\n",ans);
	}

	return 0;
	
}