神仙题。
深夜写题解感受真好
我们考虑两个简单环 (C_1,C_2)，我们假设颜色种类数为 (k)，那么我们需要有 (C_1,C_2) 均符合条件，而由于 (C_1oplus C_2) 也是环，因此我们也必须有 (C_1oplus C_2) 符合条件。不难发现 (C_1,C_2,C_1oplus C_2) 这三个环是由 (C_1-(C_1cap C_2),C_2-(C_1cap C_2),C_1cap C_2) 这三部分两两组合得到的，记 (X=C_1-(C_1cap C_2),Y=C_2-(C_1cap C_2),Z=C_1cap C_2)，那么 (C_1,C_2,C_1oplus C_2) 这三个条件均符合条件可以等价于 (X+Y,X+Z,Y+Z) 均符合条件。因此我们猜测 (C_1,C_2,C_1oplus C_2) 均符合条件的充要条件是 (X,Y,Z) 上的染色都是“均匀”的，事实也的确如此，充分性显然，必要性的话大概就如果 (X,Y,Z) 中某种颜色的出现次数大于其大小除以 (k)，那么不妨设是 (X) 中颜色 (c) 的出现次数大于 (dfrac{|X|}{k})，假设 (Delta=cnt-dfrac{|X|}{k})，其中 (cnt) 为颜色 (c) 在 (X) 中的出现次数。那么在 (Y) 中 (c) 的出现次数必然是 (dfrac{|Y|}{k}-Delta)，(Z) 也同理，这样颜色 (c) 在 (Y,Z) 中的出现次数就是 (dfrac{|Y|+|Z|}{k}-2Delta)，不符合题意。
因此我们考虑这样一个过程：将所有简单环放入一个边集组成的集合 (S)。表示对于集合 (S) 中的所有边集，其染色必须是均匀的。每次取出集合中两个有交的边集 (E_1,E_2) 并将它们删除，然后将 (E_1-(E_1cap E_2),E_2-(E_1cap E_2),E_1cap E_2) 重新加入边集，重复以上步骤直至不能再操作为止。那么进行这样的步骤之后 (S) 中的元素有什么性质呢？不难发现对于两条边 (e_1,e_2)，如果它们都在某个环上出现过，并且存在一个环 (C) 满足 (e_1in C,e_2 otin C)，那么 (e_1,e_2) 最终肯定不在 (S) 中的同一个边集中，因为咱们这个过程中只有 split，没有 merge，因此如果它们本来就不在同一个边集中，那么在接下来的过程中肯定就更不会在了。反之，而对于两条边 (e_1,e_2)，如果它们都在某个环上出现过，并且对于所有环 (C)，都有 (e_1,e_2) 要么同时被包含在 (C) 中，要么同时不属于 (C)，那么 (e_1,e_2) 肯定自始至终不会被分开，最终也肯定在同一集合中，因此我们得到性质：
Observation. 两条边 (e_1,e_2) 最终在 (S) 中的同一集合中的充要条件是，它们都在某个环上出现过，并且对于所有环 (C)，都有 (e_1,e_2) 要么同时被包含在 (C) 中，要么同时不属于 (C)。
考虑怎么将这个性质与答案挂钩。注意到我们在处理 (S) 中边集的过程中，始终有这样一条原则：对于 (S) 中所有边集，其染色必须是均匀的，即所有颜色的边在这个边集中的出现次数必须相同。因此对于最终的 (S)，其符合条件的必要条件是 (forall Ein S,kmid E)。但这是否是充要条件呢？注意到如果 (k) 符合上述约定，那如果 (S) 中所有边集我们都对其进行均匀染色，那最终每个环肯定也是均匀的，因为最终每个边集中的每条边要么同时属于某个环，要么同时不属于，它们是一个整体，不会被拆开。
也就是说，我们只要求出最终 (S) 中每个元素大小的 (gcd)，设为 (d)，那么最终答案组成的集合肯定恰好包含所有 (d) 的约数。考虑怎么求这个 (gcd)。显然我们要求出每个边集的大小对吧，那么注意到对于两个边 (e_1,e_2) 而言，其在同一个集合中等价于 (e_1,e_2) 都不是割边（否则它们就不可能在某个简单环上），并且 (G) 去掉 (e_1,e_2) 后得到的图不连通。这下就好办了，枚举每一条非割边，然后统计删掉这条边后割边的数量，然后算下与原图中割边数量的差，然后求个 (gcd) 即可。
时间复杂度 (mathcal O(m^2))。据说可以用某些神奇的随机权值+XOR 哈希的方法实现更优秀的复杂度，但是我不会（
const int MAXN=2000;
const int MAXM=2000;
int n,m,hd[MAXN+5],to[MAXM*2+5],nxt[MAXM*2+5],ec=1,ban=0,ans=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int U[MAXN+5],V[MAXN+5];bool is[MAXM+5],_is[MAXM+5];
int dfn[MAXN+5],low[MAXN+5],tim=0,res=0,_res=0;
void tarjan(int x,int f){
dfn[x]=low[x]=++tim;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f||(e>>1)==ban) continue;
if(!dfn[y]){
tarjan(y,x);chkmin(low[x],low[y]);
if(low[y]>dfn[x]) is[e>>1]=1,res++;
} else chkmin(low[x],dfn[y]);
}
}
void work(){
memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));tim=res=0;
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&U[i],&V[i]);
adde(U[i],V[i]);adde(V[i],U[i]);
} work();memcpy(_is,is,sizeof(is));_res=res;
for(int i=1;i<=m;i++) if(!_is[i]){
ban=i;work();ans=__gcd(ans,res-_res+1);
}
for(int i=1;i<=m;i++) if(ans%i==0) printf("%d ",i);
return 0;
}