Roads#776
As is well known, Ukraine faces many challenges, one of which is the condition of its roads. The transportation department has decided to focus on developing the road infrastructure. The objective is to build additional roads between cities so that it becomes possible to travel from any city to any other (possibly through intermediate cities, not necessarily directly). Naturally, as few new roads as possible should be built.
Assume that all roads in Ukraine are bidirectional—this applies to both existing and new roads to be built—so that travel in both directions is possible. Furthermore, there may be multiple roads between the same pair of cities, and roads connecting a city to itself may also exist.
The first line contains two positive integers and (1 \le n, m \le 10000) — the number of cities and the number of existing roads. Each of the following lines contains two integers a_i and b_i (1 \le a_i, b_i \le n) — the numbers of the cities connected by an existing road.
Output the minimum number of roads that must be built so that it is possible to travel from any city to any other.
Example 1