P6914 [ICPC 2015 WF] Tours

题目描述

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

保证图无重边，无自环。

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1

输入输出样例 #2

输入 #2

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

输出 #2

1 3