[Wf2015]Tours

时间限制:3s      空间限制:128MB

题目描述

给定一张n个点m条边的无向图,你需要选择一个颜色种类数k,然后用这k种颜色给每条边染色,要求对于图中任意一个简单环,每种颜色的边的数量都相同,求所有可行的k


输入格式

第一行两个正整数n,m
接下来m行,每行两个正整数x,y(1<=x<y<=n),代表一条无向边
数据保证无重边无自环


输出格式

一行输出所有可行的k,按递增顺序输出 6 6 1 2 2 3 1 3 1 4 2 5 3 6


样例输入

6 6
1 2
2 3
1 3
1 4
2 5
3 6

样例输出

1 3

提示

 n,m<=2000


题目来源

鸣谢王天懿提供题面