Difficult Routes#3046
In preparation for the upcoming Olympics, you are asked to propose bicycle training routes for your country's team. The training committee seeks to identify routes between pairs of locations at various sites throughout the country. Each route must have a specified level of difficulty based on the steepness of its hills.
You will be given a road map with elevation data. Each intersection, where two or more roads meet, is identified by its -, -, and -coordinates. Each road starts and ends at an intersection, is straight, and does not cross over or under other roads (i.e., no bridges or tunnels). The difficulty level for cycling a road is if the road is level or is traveled in the downhill direction. For an uphill (non-level) road, the difficulty is 100 \cdot \text{rise}/\text{run}, where is the absolute change in elevation, and is the distance between its two intersection points in its horizontal projection onto the D-plane at elevation zero. Note: the difficulty for descending a road is always zero.
A route—a sequence of roads where the next road continues from the intersection where the previous one ends—has a level of difficulty if the maximum difficulty among all its roads equals . The committee also wants, if such a route with the specified difficulty exists between two selected locations, the route with the shortest possible total length.
Reminder: The floor function means truncated to an integer.
Input consists of several road maps. Each map's description begins with two non-negative integers and (separated by a space, each on its own line), representing the number of intersections and the number of roads, respectively (0 < N, M \leq 10000). A line with N = 0 and M = 0 marks the end of input.
Each of the next lines contains three integers separated by spaces, representing the -, -, and -coordinates of an intersection (0 \leq x, y, z \leq 10000). Intersections are numbered in the order they appear, starting from one. The next lines each contain two integers representing the start and end intersection numbers of a road.
Finally, three integers , , and specify the starting intersection , ending intersection , and the required difficulty level for the training route (0 \leq d \leq 10). A valid training route must have at least one road with difficulty level and no road with difficulty greater than . If a closed circuit is required, then and refer to the same intersection.
For each road map and requested route, output a single line containing:
the length of the shortest valid training route, rounded to one decimal place, or
the single word None, if no suitable route exists.
Reminder: Rounding a positive number to three decimal places
If the fourth decimal digit is less than , the rounded value is
Otherwise, the rounded value is R.xxx + 0.001
Examples: for , the output should be ; for , the output may be either or .
Example 1