Boa#761
A boa has escaped from the zoo in the city of Ensk. While fleeing, it entered the local sewer system. The sewer consists of several wells connected by straight horizontal pipes, with all wells except two covered by lids. The boa entered through one open well and wants to exit through the other open well, choosing the shortest possible route. However, since the boa is old and suffers from rheumatism, it can only bend up to a maximum angle of (that is, when moving from one pipe to another, the direction change cannot exceed ). You must determine the shortest route through the sewer from one open well to the other, such that the path never bends by more than at any well (see the example). The boa can move from one pipe to another only at a well that is an endpoint of both pipes. The boa can crawl in either direction along any pipe.
The first line contains three integers separated by spaces: , , (1 < N \le 50, 0 \le M \le 1225, 0 \le \alpha \le 180), where is the number of wells, and is the number of pipes connecting the wells. The next line contains the numbers of the starting and ending wells. The following lines contain the coordinates of the wells (two integers per line, each not exceeding in absolute value). The next lines describe the pipes, each line containing two numbers indicating the wells connected by a pipe. Wells are numbered from one.
Print a single number: the length of the shortest route, to three decimal places, or if there is no such route. If a route exists, print in the next line the sequence of well numbers in the route, separated by spaces.
Example 1