SuccessfulMerger

In the country of Byteland, there are N cities connected by N bidirectional roads (that is, the number of roads is the same as the number of cities). The cities are numbered from 0 to N-1. For each i from 0 to N-1, a bidirectional road connects city i and city road[i]. (Note that sometimes a pair of cities can be connected by two distinct roads.) It is possible to travel between any pair of cities using the network of roads.

You are the prime minister of Byteland and you must choose one of the cities to be the capital city. The capital city must have the following property: whenever A and B are two distinct cities, it must be impossible to travel between A and B without visiting the capital.

If there is no valid location for the capital, you must create one. In order to do that, you may modify the road network by doing a sequence of mergers. A merger is an operation that merges two adjacent cities into a single new city. Formally, a merger is performed as follows:

• You select two cities X and Y that are directly connected by a road. (They may even be connected by more than one direct road.)
• The two cities are merged together to create a new city Z.
• All direct roads between X and Y disappear. Each other road that connected X or Y to some other city now connects Z to that other city.

For example, suppose this is the network:



There is no valid location for the capital. However, by merging city 1 and city 2, we can create a valid location:



Now the newly-created city is a valid location for the capital.

You are given the description of the road network in the int[] road. Please find and return the minimum number of mergers necessary to create a valid location for the capital.