Edges removal

The undirected graph without loops and multiple edges is given. Remove the minimum number of edges to make a graph disconnected.

Input

Two numbers n and k (2 ≤ n ≤ 100, 0 ≤ k ≤ n·(n-1)/2) - the number of vertices and edges in a graph. Then given k lines, each contains two numbers - a and b (1 ≤ a, b ≤ n) - the numbers of the vertices, connected with an edge.

Output

One number - the minimum number of edges to make a graph disconnected.

Examples