순환 관광 코스

아르카 카라니아 산 국립공원이 관광객을 맞이한다. 공원에는 둘러볼 만한 명소가 여럿 있고, 두 명소를 잇는 도로가 놓여 있다. 관리위원회는 관광객이 버스를 타고 명소를 도는 순환 관광 코스를 정리해 두었다. 순환 코스는 어떤 명소에서 출발해 다른 명소를 한 번씩만 지난 뒤 출발한 명소로 돌아온다. 코스마다 출발 명소는 다를 수 있다. 코스 하나가 들르는 명소는 3곳 이상이다. 공원에는 순환 코스가 적어도 하나 있다.

관리위원회는 도로 하나의 버스 운행을 회사 한 곳에 통째로 맡기기로 했다. 특정 회사를 밀어준다는 말을 듣고 싶지 않아서, 공원에서 가능한 모든 순환 코스마다 회사가 맡은 도로의 수가 정확히 같기를 바란다. 이런 배정이 어렵다는 것도 알고 있다. 그래서 회사가 몇 곳일 때 도로를 제대로 배정할 수 있는지 알고 싶어 한다.

명소가 4곳이고 도로가 1-2, 2-3, 3-4, 1-4, 1-3인 공원을 보자. 순환 코스는 1-2-3-1, 1-3-4-1, 1-2-3-4-1로 모두 셋이다. 도로 1-3을 맡은 회사는 코스 1-2-3-4-1에서도 도로를 하나 맡아야 하니, 그 회사가 2-3을 맡았다고 하자. 그러면 이 회사는 코스 1-2-3-1의 도로 3개 중 2개를 맡게 되고, 다른 어떤 회사도 같은 수를 맡을 수 없다. 따라서 회사는 한 곳뿐이어야 한다. 반대로 순환 코스가 하나뿐인 공원이라면 그 코스의 도로를 회사들에 고르게 나눠 주기만 하면 된다.

첫 줄에 명소의 수 $n$ ($1 \le n \le 2000$)과 도로의 수 $m$ ($1 \le m \le 2000$)이 주어진다. 다음 $m$개의 줄에는 각각 두 정수 $a_i$와 $b_i$ ($1 \le a_i < b_i \le n$)가 주어진다. 명소 $a_i$와 $b_i$가 양방향 도로로 이어져 있다는 뜻이다. 같은 명소 쌍이 두 번 주어지지는 않는다.

원하는 방식으로 도로를 $k$개 회사에 배정할 수 있는 정수 $k$를 모두 구해, 오름차순으로 한 줄에 공백 하나로 구분해 출력한다.