Travel and Minimum Flights

You are given n cities and m direct flights. Each flight connects two distinct cities bidirectionally. The task is to determine whether it is possible to travel between any two cities using only these flights. If the entire graph (the network of cities) is connected, then you should output the minimum number of flights required to visit all cities, which is given by the formula \(n-1\). Otherwise, output -1.

In other words, if the cities form a connected graph, the answer is \(n-1\) (since a connected graph with \(n\) nodes has at least \(n-1\) edges). Use standard graph traversal techniques (such as Breadth-First Search) or the union-find data structure to check connectivity.

inputFormat

The first line of input contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of cities and \(m\) is the number of flights.

Each of the following \(m\) lines contains two integers \(u\) and \(v\), representing a direct bidirectional flight between city \(u\) and city \(v\).

outputFormat

Output a single integer: the minimum number of flights required to visit all cities if it is possible to travel between any two cities. Otherwise, output -1.

4 4
1 2
2 3
3 4
4 1

3