题目描述

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

输入格式

第一行两个正整数$n,m$

接下来$m$行，每行两个正整数$x,y(1\le x<y\le 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

数据范围与约定

对于$100\%$的数据:$n,m\le 2000$.