Minimize Edge Removals to Form a Tree

You are given an undirected graph with N vertices and M edges. Your task is to determine the minimum number of edges that must be removed so that the resulting graph is a tree. If it is impossible to obtain a tree, output -1.

A tree is defined as an acyclic connected graph with exactly N - 1 edges. Given the graph in the form of a list of edges, you need to check if the graph is connected. If not, it is impossible to form a tree, and you should output -1. Otherwise, the answer is the number of extra edges in the graph, i.e. M - (N - 1).

The mathematical formulation is as follows:

Let \(N\) be the number of vertices and \(M\) be the number of edges. A tree requires exactly \(N - 1\) edges. If \(M < N - 1\) or the graph is not connected, output \(-1\). Otherwise, the minimum number of removals is given by:

[ \text{answer} = M - (N - 1)]

inputFormat

The first line contains two integers N and M separated by a space.

Each of the following M lines contains two integers u and v denoting an undirected edge between vertices u and v.

outputFormat

Output a single integer: the minimum number of edges that need to be removed to form a tree. If it is impossible to form a tree, output -1.

## sample

6 6
1 2
2 3
3 4
4 5
5 6
1 6

1