K-그래프 홀수성

정점의 개수가 홀수인 연결 무방향 그래프가 주어진다. 한 정점의 차수(degree)는 그 정점에 연결된 간선의 개수이다.

이러한 그래프는 항상 적절한 색칠이 가능하다는 사실이 잘 알려져 있다. 즉, 인접한 두 정점이 서로 다른 색을 가지도록 모든 정점에 색을 부여할 수 있으며, 이때 최대 $k$가지 색만 있으면 충분하다. 여기서 $k$는 그래프의 최대 차수보다 크거나 같은 가장 작은 홀수이다.

그래프가 주어졌을 때, 이 값 $k$를 구하여라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다. $n$은 정점의 개수이고 ($3 \le n \le 9999$, $n$은 홀수), $m$은 간선의 개수이다 ($2 \le m \le 100\,000$).

이어지는 $m$개의 줄에는 각각 두 정수 $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$)가 주어지며, 이는 정점 $a_i$와 $b_i$를 잇는 간선을 나타낸다. 각 간선은 최대 한 번만 주어진다. 그래프는 연결되어 있으므로 임의의 두 정점 사이에는 항상 경로가 존재한다.

모든 정점의 차수가 $k$를 넘지 않도록 하는 가장 작은 홀수 $k$를 한 줄에 출력한다. (즉, 그래프의 최대 차수보다 크거나 같은 가장 작은 홀수를 출력한다.)