记录编号	313810	评测结果	AAAAAAAAAA
题目名称	[Nescafé 17] 黑魔法师之门	最终得分	100
用户昵称	Tiny	是否通过	通过
代码语言	C++	运行时间	0.675 s
提交时间	2016-10-02 07:33:11	内存使用	0.30 MiB

#include <stdio.h>

template <typename T> inline void Read(T &num) {
	num = 0; char ch; bool minus = false;
	while (ch = getchar(), ch < '-' || ch > '9');
	if (ch == '-') minus = true, ch = getchar();
	while (num = num * 10 + ch - '0', ch = getchar(), ch >= '0' && ch <= '9');
	if (minus) num = -num;
}

const size_t maxn = 200000 + 10;

class UFS {
	int fa[maxn];

	inline int Findfa(const int &x) { return fa[x] == x ? x : fa[x] = Findfa(fa[x]); }

public:
	inline UFS(const int &n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

	inline void link(const int &x, const int &y) { fa[Findfa(x)] = Findfa(y); }

	inline bool linked(const int &x, const int &y) { return Findfa(x) == Findfa(y); }
} *ufs;

#define SUBMIT

int main() {
 #ifdef SUBMIT
	freopen("magiciana.in", "r", stdin);
	freopen("magiciana.out", "w", stdout);
 #endif

	int n, m;
	Read(n); Read(m);
	ufs = new UFS(n);
	int u, v, ans = 0;
	for (int i = 1; i <= m; ++i) {
		Read(u); Read(v);
		if (!ufs->linked(u, v)) ufs->link(u, v);
		else ans = (ans * 2 + 1) % 1000000009;
		printf("%d\n", ans);
	}

 #ifndef SUBMIT
	puts("\n--------------------");
	getchar(); getchar();
 #else
	fclose(stdin); fclose(stdout);
 #endif
	return 0;
}