K-Graph Oddity

Interview

Time limit1sMemory limit128 MB

Summary

Compute the maximum vertex degree in a graph and output the smallest odd integer greater than or equal to it.

Level: Easy2 of 10
Topics: Graph, Implementation, Math
Solved: No attempts yet

Problem

You are given a connected undirected graph with an odd number of vertices. The degree of a vertex is the number of edges incident to it.

It is a well-known fact that such a graph can always be properly colored — that is, every vertex can be assigned a color so that no two adjacent vertices share the same color — using at most $k$ colors, where $k$ is the smallest odd integer that is greater than or equal to the maximum degree of the graph.

Given the graph, determine this value $k$ .

Input

The first line contains two integers $n$ and $m$ : the number of vertices $n$ ( $3 \le n \le 9999$ , $n$ is odd) and the number of edges $m$ ( $2 \le m \le 100\,000$ ).

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le n$ , $a_i \ne b_i$ ) describing an edge between vertices $a_i$ and $b_i$ . Each edge is listed at most once. The graph is connected, so there is a path between every pair of vertices.

Output

Output a single integer $k$ — the smallest odd integer such that the degree of every vertex does not exceed $k$ (equivalently, the smallest odd integer that is greater than or equal to the maximum vertex degree).

Examples4

Example 1
Input
```
3 2
1 3
3 2
```
Expected output
```
3
```
Example 2
Input
```
7 8
1 4
4 2
2 6
6 3
3 7
4 5
5 6
5 2
```
Expected output
```
3
```
Example 3
Input
```
5 4
1 2
1 3
1 4
1 5
```
Expected output
```
5
```
Example 4
Input
```
3 3
1 2
2 3
1 3
```
Expected output
```
3
```