Question Description

Given an undirected graph with $n$ vertices and $m$ edges, you need to choose a number of color types $k$, and then use these $k$ colors to color each edge. For any simple cycle in the graph, the number of edges of each color should be the same. Find all feasible $k$

Input format

The first line contains two positive integers $n, m$

Next, $m$ lines, each line containing two positive integers $x,y(1\le x<y\le n)$ representing an undirected edge

The data ensures no multiple edges and no self-loops

Output format

Output all possible values of $k$ on one line

Example

Note: Input $6$ $6$ $1$ $2$ $2$ $3$ $1$ $3$ $1$ $4$ $2$ $5$ $3$ $6$ in increasing order

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

1 3

Data Range and Conventions

For $100\%$ of the data: $n,m\le 2000$.