Galaxy Quest

You are travelling through the galaxy in your spaceship. There are $n$ planets, numbered from $1$ to $n$, and each planet is modelled as a point in 3-dimensional space.

You can travel between these planets along $m$ space highways. Each highway follows the straight line that connects its two planets. Your engine can accelerate (or decelerate) at $1\text{m/s}^2$, and it uses 1 litre of fuel per second. There is no limit to how fast you can go, but you must come to a complete standstill each time you arrive at the planet at the end of a highway.

A highway may pass through planets other than the two it connects. Your ship has hyperspace technology, so it phases through those planets without stopping. You cannot switch from one highway to another midway, so every highway must be travelled in full.

Figure G.1: Illustration of the first sample input. Highways are drawn in blue, and the route from planet 1 to planet 3 is shown. The green start of a highway marks acceleration, and the red end marks deceleration. The figure shows the optimal route for the second mission.

You need to fly several missions. In each mission you start at your home planet (planet 1) and must reach a given target planet within a given time limit. For each mission, determine whether it can be completed, and if so, find the least amount of fuel required.

The first line contains three integers $n$, $m$, and $q$ ($1 \le n,m,q \le 10^5$, $n \ge 2$), where $n$ is the number of planets, $m$ is the number of highways, and $q$ is the number of missions.

The next $n$ lines each contain the coordinates $x_i$, $y_i$, and $z_i$ of planet $i$, in metres ($|x_i|,|y_i|,|z_i| \le 10^3$, $1 \le i \le n$).

The next $m$ lines each contain two integers $a$ and $b$ ($1 \le a,b \le n$, $a \neq b$), describing a highway that connects planets $a$ and $b$. A highway can be traversed in either direction.

The last $q$ lines each contain a target planet $c$ and a time limit $t$ in seconds ($2 \le c \le n$, $1 \le t \le 10^3$).

All planets are at distinct locations. No two highways connect the same pair of planets. For each mission, both the absolute and the relative difference between the time limit and the shortest possible completion time are at least $10^{-6}$.

For each mission, print the least amount of fuel in litres needed to reach the target planet within the time limit. If the target cannot be reached in time, print impossible. Answers are accepted with an absolute or relative error of at most $10^{-6}$.