Equal Company Assignment on Round Tours

The Arca Carania Mountain national park is opening up for tourist traffic. The park has several sites connected by roads. A round tour is defined as a simple cycle (with at least three distinct sites) that starts and ends at the same site. The park commissioners plan to assign each road to a bus company. They require that for any possible round tour the edges (roads) are distributed equally among the companies.

Formally, suppose that a round tour has L roads. If there are k companies available, every company must operate exactly \(\frac{L}{k}\) roads on that tour. In other words, \(k\) must divide L for every round tour in the park. Let \(g\) be the greatest common divisor (\(\gcd\)) of the lengths of all (simple) cycles in the graph. Then a valid assignment of companies exists if and only if k is a divisor of \(g\).

Your task is to determine all possible numbers of bus companies (i.e. all positive divisors of \(g\)) for which a valid assignment exists.

Hint: You may compute a fundamental cycle basis by running a DFS on the undirected graph. For each back edge from a vertex \(u\) to an ancestor \(v\), the cycle length is \(\text{depth}[u] - \text{depth}[v] + 1\). The \(\gcd\) of all these cycle lengths is \(g\), and the answer is all positive divisors of \(g\) sorted in increasing order.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of sites and roads respectively. The following \(m\) lines each contain two integers \(u\) and \(v\) indicating that there is an undirected road between sites \(u\) and \(v\). It is guaranteed that there is at least one round tour in the park.

outputFormat

Output all possible numbers of bus companies (i.e. all positive divisors of \(g\)) in increasing order separated by a space.

sample

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

1