Boa
A python has escaped from the zoo in the city of Ensk. While evading capture, it slithered into the local sewer system. This system consists of several wells connected by straight horizontal pipes, with all wells except two covered by lids. The python entered through one of the open wells and aims to exit through the other. Naturally, it seeks the shortest possible path. However, due to its age and rheumatism, the python can only bend at a maximum angle of α (meaning the direction change between two pipes cannot exceed angle α). Your task is to find the shortest path through the sewer from one open well to the other, ensuring that the python's path does not bend more than angle α at any point (refer to the example). The python can only transition from one pipe to another at a well that serves as an endpoint for both pipes. It can move in any direction along a pipe.
Input
The first line of the input contains three integers separated by spaces: N, M, and α (1 < N ≤ 50, 0 ≤ M ≤ 1225, 0 ≤ α ≤ 180), where N is the number of wells, and M is the number of pipes connecting these wells. The next line specifies the numbers of the starting and ending wells for the route. The following N lines provide the coordinates of the wells (two integers, each not exceeding 10000 in absolute value). The next M lines detail the pipes, with each line containing two numbers indicating the wells connected by that pipe. Wells are numbered starting from one.
Output
The first line of the output should contain a single number: the length of the shortest route, accurate to three decimal places, or –1 if no such route exists. If a route is found, the next line should list the sequence of well numbers in the route, separated by spaces.