Description

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

保证图无重边，无自环。

Input Format

第一行两个正整数 $n, m$（$1\leq n, m\leq 2\times 10 ^ 3$）。

接下来 $m$ 行，每行两个正整数 $x, y$（$1\leq x < y \leq n$），表示一条无向边。

Output Format

一行按递增顺序输出所有可行的 $k$，用空格隔开。

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

1

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

1 3