Minimum Edge Removals for Desired Components

You are given an undirected graph with n nodes and m edges. Your task is to determine the minimum number of edges to remove so that the graph becomes separated into exactly k connected components.

More formally, let the initial number of connected components be \( c \). By removing an edge that is a bridge (an edge whose removal increases the number of connected components), you can split one connected component into two. In a connected component of size \( s \), you can remove at most \( s-1 \) bridges in order to split it into \( s \) individual nodes, achieving the maximal possible components from that part.

The goal is to achieve exactly \( k \) components. Thus if it is possible, the minimum number of edges to remove is \( k - c \), provided that \( k \le n \) (since you cannot have more than \( n \) components) and \( c \le k \). Otherwise, output -1.

Input constraints and details: The first line contains three integers n, m, and k. Then there are m lines, each containing two integers representing an undirected edge between two nodes.

Note: Use \( \LaTeX \) format for formulas.

inputFormat

The first line of input contains three space‐separated integers \( n \), \( m \), and \( k \), the number of nodes, edges, and the desired number of connected components respectively.

Each of the next \( m \) lines contains two integers \( u \) and \( v \), indicating that there is an undirected edge between nodes \( u \) and \( v \>.

outputFormat

Output a single integer denoting the minimum number of edges to remove so that the graph has exactly \( k \) connected components. If it is impossible to achieve exactly \( k \) components, output -1.

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

2