本文共 950 字，大约阅读时间需要 3 分钟。

经过了16个工作日的紧张忙碌，未来的人类终于收集到了足够的能源。然而在与Violet星球的战争中，由于Z副官的愚蠢，地球的领袖applepi被邪恶的黑魔法师Vani囚禁在了Violet星球。为了重启Nescafe这一宏伟的科技工程，人类派出了一支由XLk、Poet_shy和lydrainbowcat三人组成的精英队伍，穿越时空隧道，去往Violet星球拯救领袖applepi。

Input

第一行包含两个整数N和M。

Output

输出一共M行，表示每次操作后的密码。

其实可以发现，这些子图都是环。

#include
   
    int n,m,f[200001],x,y,ans;int find(int d){      //寻找f节点	if(f[d]!=d) f[d]=find(f[d]);  //压缩路径	return f[d];}int main(){   	scanf("%d%d",&n,&m);	for(int i=1;i<=n;++i)   //复制成自己	  f[i]=i;	for(int i=1;i<=m;++i){   		scanf("%d%d",&x,&y);		if(find(x)!=find(y)) f[find(x)]=find(y);   //这俩个没形成环		else ans=(ans*2+1)%1000000009;    //形成了环之后，与之前的环可以相交的个数+自己		printf("%d\n",ans);  //输出	}}