제목 설명

$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$ $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$.