Description

We say that an undirected graph is connected if,for every pair of nodes u and v,there is a path from u to v. Hence the problem is given a undirected but connected graph,output the maximum edges which can be deleted left the graph still connected.

Input

The first line is the number of vertexes N(1v2).There will not be any duplicate edges. Be careful for more cases.

Output

print only a line for each case with the number of maximum edges deledted.

Sample

Input

3 4
1 2
2 3
1 3
2 3

Output

2