Eco-driving
My colleague Elisabeth is lazy, both at work and when going to work. She never wants to do more than necessary, which also applies to her journey to work. Her goal is to use a minimum amount of energy, which she achieves by braking and accelerating as little as possible. This method applies to all wheel-based transport means she owns.
Elisabeth has earlier optimized her route by trial and error, but now wants your help to find the optimal path. She has provided a map with n junctions and r straight one-way roads between the junctions. If a road is dual way, it is represented as two one way roads.
Fortunately, Elisabeth often works night shifts, so braking and acceleration are only needed when turning in a junction, as there is no other traffic on the roads. Her goal is to find a route where the maximum turning angle in the junctions is minimized, as this means maximized speed. However, the route can not be too long.
Input
The first line contains three space separated integers j (2 ≤ j ≤ 200), r (1 ≤ r ≤ 39800) and d (1 ≤ d ≤ 1000000). j is the number of junctions, r is the number of one way roads which are connecting two junctions, and d is the maximum distance, in meters, that Elisabeth wants to travel. The road network is such that there is no path, that Elisabeth may want to use, which has the length l such that d < l < d · (1 + 10^(-6)).
Then follow j lines with two integers x and y (-100000 ≤ x, y ≤ 100000), the distinct coordinates in meters on a flat ground. Elisabeth lives at junction 1 and her work is at junction j. After that r lines follow with two integers a and b. This should be interpreted as the one way road between the one-indexed source and destination junctions a and b (1 ≤ a, b ≤ j).
Output
Output one line with the maximum turning angle of the route that the maximum turning angle as low as possible. The turning angle must be output in degrees and have an absolute or relative error at most 10^(−6). If there is no such route that is short enough, output "Impossible" on a single line.