題目描述

給定一張$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$.