The Kingdom of Byteland consists of several cities connected by bidirectional roads. There are castles standing in some of the cities. Byteasar, the King of Byteland is unhappy with his kingdom's defensive power, so he decided to build k additional castles (he can only afford that many).
Whenever one of the cities is attacked by the enemy, the army from the nearest castle must come with help. The enemy is smart, so it will always find and attack the city that is the farthest away from its nearest castle. Therefore, the distance from the attacked city to its nearest castle must be as small as possible. Your job is to calculate and return this distance, assuming that you can decide where to build the k additional castles.
The cities are built in a specific manner. Each city has a main gate and several other gates. Every gate is connected to another gate by a road. It is possible that two gates of the same city are connected (see example 2). For defensive reasons, every road has exactly one main gate on one of its ends. Please note that every road can be traversed in both directions.
The road going out of the main gate of the i-th city leads to the road[i]'th city and is distance[i] miles long. The int castles contains the 0-based indices of the cities in which a castle is already built.