Eco-driving

My colleague Elisabeth is lazy — both at work and on her way to work. She never does more than necessary, and that includes her commute. Her goal is to spend as little energy as possible, which she achieves by braking and accelerating as little as she can. This applies to every wheeled vehicle she owns.

Elisabeth has already tuned her route by trial and error, but now she wants your help to find the optimal one. She gives you a map with $J$ junctions and $R$ straight one-way roads between them. A two-way road is represented as two separate one-way roads.

Because Elisabeth often works night shifts, there is no other traffic on the roads, so she only needs to brake and accelerate when she turns at a junction. She wants a route on which the largest turning angle at any junction is as small as possible, because that lets her keep her speed up. However, the route must not be too long.

The turning angle at a junction is the angle between the direction of the road she arrives on and the direction of the road she leaves on. It ranges from $0$ degrees (continuing straight ahead) to $180$ degrees (turning completely back). Taking the first road out of junction $1$ requires no turn, and arriving at junction $J$ ends the trip, so no turn is counted there.

The first line contains three space-separated integers $J$, $R$, $D$ ($2 \le J \le 200$, $1 \le R \le 39\,800$, $1 \le D \le 1\,000\,000$): the number of junctions, the number of one-way roads, and the maximum distance in meters that Elisabeth is willing to travel. The road network is such that no path she might use has a length $L$ with $D < L < D \cdot (1 + 10^{-6})$.

Then follow $J$ lines, each with two integers $X$ and $Y$ ($-100\,000 \le X, Y \le 100\,000$): the distinct coordinates in meters of the junctions on flat ground. Elisabeth lives at junction $1$ and works at junction $J$.

Then follow $R$ lines, each with two integers $A$ and $B$ ($1 \le A, B \le J$), describing a one-way road from source junction $A$ to destination junction $B$.

Output a single line with the largest turning angle, in degrees, of the route whose largest turning angle is as small as possible, rounded to exactly $8$ digits after the decimal point. If no route from junction $1$ to junction $J$ is short enough (total length at most $D$), output Impossible instead.