Skills Training 4

The G.W. Williams coding club execs have a 2d Christmas tree for sale, with \(N\) Christmas lights all around its surface. Each of these \(N\) lights are the same space apart and connected by multiple bidirectional wires.

The execs know that one of the \(N\) lights lies on the bottom of the tree, and one of the \(N\) lights lies on the top. However, they do not know the height of the tree. They also know the distance between each light is constant, and the light on the bottom of the tree and the light on the top of the tree have the most wire in between them compared to any other pair of lights in the whole tree.

So, the execs decide to approximate the height of the tree using this information. The method they use is to find the number of wire connections between the bottom light and the top light.

Given \(N\) number of lights on the first line, and \(M\) connections of the lights, can you help the execs approximate the height of the tree?

Submit Solution