{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eIn preparation for the coming Olympics, you have been asked to propose bicycle training routes for your country\u0027s team. The training committee wants to identify routes for traveling between pairs of locations in multiple sites around the country. Each route must have a desired level of difficulty based on the steepness of its hills. \u003cbr\u003eYou will be given a road map with the elevation data superimposed upon it. Each intersection, where two or more roads meet, is identified by its x- , y- , and z-coordinates. Each road starts and ends at an intersection, is straight, and does not contain bridges over or tunnels under other roads. The difficulty level, d, of cycling a road is 0 if the road is level or travelled in the downhill direction. The difficulty of a non-level road when travelled in the uphill direction is\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/0c84ef753f527254bc83e8d8ac660207?v\u003d1714284580\"\u003e100*rise / run\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/ef9acc1509509d05e07a8064f715567b?v\u003d1714284580\"\u003e . Here rise is the absolute value of change in elevation and run is the distance between its two intersection points in its horizontal projection to the 2D-plane at elevation zero. Note that the level of difficulty for cycling a descending road is zero.\u003cbr\u003eA route, which is a sequence of roads such that a successor road continues from the same intersection where its predecessor road finishes, has a level of difficulty d if the maximum level of difficulty for cycling among all its roads equals d. The committee is also interested in the chosen route between two selected locations, if such a route with the desired difficulty level exists, being the one with the shortest possible distance to travel.\u003cbr\u003eReminder: The floor function \u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/7ebb97cca20a398d46b724504659b36d?v\u003d1714284580\"\u003eX\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/008dcb3a1f6c176bc3bf73a662ec70d3?v\u003d1714284580\"\u003e means X truncated to an integer.\u003cbr\u003eThe figure shows a road map with three intersections for the three sample inputs.\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/7444472b11f2f66437724cd167f5cd7d?v\u003d1714284580\"\u003e\u003c/center\u003e\u003cbr\u003eThe edge labels of the darker shaded surface give the level of difficulty of going up hill. The lighter shaded surface is the horizontal projection to the 2D-plane at elevation zero.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Input consists of many road maps. Each map description begins with two non-negative integers N and M, separated by a space on a line by themselves, that represent the number of intersections and the number of roads, respectively. N \u0026lt;\u003d 10000, M \u0026lt;\u003d 30000. A value of both N and M equal to zero denotes the end of input data.\u003cbr\u003eEach of the next N lines contains three integers, separated by single spaces, which represent the x-, y- and z-coordinates of an intersection. The integers have values between 0 and 10000, inclusive. Intersections are numbered in order of their appearance starting with the value one. Each of the following M lines contains two integers that represent start and end intersections of a road.\u003cbr\u003eFinally, three integers s, t and d that represents the desired starting intersection number s, the finishing intersection number t and the level of difficulty d for a training route are given on line by themselves. A valid training route must have at least one road with a difficulty level of d, and no road with a difficulty level greater than d. 0 \u0026lt;\u003d d \u0026lt;\u003d 10. If the training route is meant to form a closed circuit, then s and t are the same intersection numbers."}},{"title":"Output","value":{"format":"HTML","content":"For each road map and desired route, the output consists of a single line that contains:\u003cbr\u003e1. number denoting the shortest length of a training route rounded to one decimal places, or\u003cbr\u003e2. the single word “None” if no feasible route exists."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\r\n0 0 0\r\n100 100 6\r\n200 0 7\r\n1 2\r\n2 3\r\n3 1\r\n1 2 3\r\n3 3\r\n0 0 0\r\n100 100 6\r\n200 0 7\r\n1 2\r\n2 3\r\n3 1\r\n1 1 4\r\n3 3\r\n0 0 0\r\n100 100 6\r\n200 0 7\r\n1 2\r\n2 3\r\n3 1\r\n2 1 5\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e341.5\r\n283.1\r\nNone\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}