Sensor network

In response to a request by the SWERC 2010 problem-setting team, a sensor network has just been installed in the headquarters. The organizing committee has instilled in the problem-setters a disproportionate fear of leaking classified information about the problems.

However, in their haste, they forgot to consider the electrical network needed to make the sensors work. As a result, the security system is currently not working, but the large amount of resources spent on it needs to be justified, so the installation must be ready before the contest ends. Therefore, you are asked to write a program to assist the electrician in his work.

Since the organizing committee spared no expense, they ordered the sensors from a prestigious company. Every sensor is handcrafted, and each one has a number written on it, indicating the recommended voltage that should be applied for correct operation. Sensors can function at higher voltages, though this increases the risk of failure, but they should never be used with a voltage below the recommended value. The electrician was surprised when he received the sensors: almost all of them had different recommended voltages! The sensors were installed in the building so that each one controls exactly two doors, and every door is controlled by at least one sensor. Now it is time for the electrician to supply power to the sensors. He faces the following constraints:

• Fortunately, it is not necessary to activate all the sensors. However, it is required that the chosen subset of sensors to be activated ensures that every door is controlled by at least one sensor in the subset.

• Electricity is to be supplied to one of the active sensors, and then distributed to the others using wires. To avoid wasting wires, they can only be installed by connecting a pair of neighboring active sensors ("neighboring" means they both control the same door). Since every active sensor must receive power, not every subset of sensors is suitable to be the chosen working set.

• Due to the above, all activated sensors will be supplied with the same voltage, which cannot be below their corresponding recommended voltages.

For simplicity, a subset of sensors satisfying the first two constraints above is called an admissible subset. The network is designed so that the set of all sensors is always an admissible subset, but it is preferable to select a possibly smaller subset that minimizes the margin, defined as the maximum difference, in absolute value, between the numbers written on any pair of sensors in the subset. (This is to keep the risk of failure as low as possible).

The electrician could not solve the problem of finding the admissible subset of sensors with the minimum margin. Therefore, the electrical installation is still not complete. Today, you are asked to write a program to find the answer, given the sensor network and the recommended voltage for each sensor.