Minimum Paths to Connect Cities

You are given an integer n representing the number of cities. The task is to determine the minimum number of bidirectional communication paths (roads) that need to be constructed so that every pair of cities has a communication route between them.

This problem can be interpreted as connecting n nodes in a graph with the minimum number of edges. Recall that a tree with n nodes has exactly n-1 edges. In this context, the minimal number of communication paths required is given by the formula: \(n - 1\).

For example, if there are 4 cities, the answer is 3, since \(4 - 1 = 3\).

inputFormat

The input consists of a single line containing one integer n (where n \ge 2), representing the number of cities.

outputFormat

Output a single integer which is the minimum number of bidirectional communication paths required to ensure that there is a route between every pair of cities.

4

3