레이팅 미적용You are travelling through the galaxy in your spaceship. There are \(n\) planets in the galaxy, numbered from \(1\) to \(n\) and modelled as points in \(3\)-dimensional space.
You can travel between these planets along \(m\) space highways, where each highway connects two planets along the straight line between them. Your engine can accelerate (or decelerate) at \(\SI{1}{\metre\per\second\squared}\), while using fuel at a rate of \(1\) litre per second. There is no limit to how fast you can go, but you must always come to a complete standstill whenever you arrive at the planet at the end of a highway.
It is possible for a highway to pass through planets other than the ones it connects. However, as your spaceship is equipped with special hyperspace technology, it simply phases through these obstacles without any need of stopping. Another consequence of using this technology is that it is impossible to jump from one highway to another midway through: highways must always be travelled in full.
You need to fly several missions, in which you start at your home planet (with number \(1\)) and need to 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 to do so. As an example, Figure shows the optimal route for the second mission of the first sample.
The input consists of:
- One line with 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 space highways, and \(q\) is the number of missions.
- \(n\) lines, each with three integers \(x_i\), \(y_i\), and \(z_i\) (\(\left|x_i\right|,\left|y_i\right|,\left|z_i\right| \le 10^3\), \(1 \le i \le n\)), the coordinates of planet \(i\).
- \(m\) lines, each with two integers \(a\) and \(b\) (\(1 \le a,b \le n\), \(a \neq b\)), describing a space highway that connects planets \(a\) and \(b\). It can be traversed in either direction.
- \(q\) lines, each with two integers \(c\) and \(t\) (\(2 \le c \le n\), \(1 \le t \le 10^3\)), the target planet and time limit for each mission.
The \(n\) planets are in distinct locations. Their coordinates are given in metres, and the time limits of the missions are given in seconds. No two highways connect the same pair of planets. For each mission, both the absolute and relative differences between the given time limit and the shortest possible completion time are at least \(10^{-6}\).
For each mission, output the least amount of fuel in litres required to reach the target location within the time limit. If the target location cannot be reached within the time limit, output "impossible".
Your answers should have an absolute or relative error of at most \(10^{-6}\).
4 4 3
-30 0 0
0 0 0
50 0 0
-30 10 0
1 2
2 3
3 4
4 1
2 10
3 25
4 7
impossible
19.0538441903
4.0000000000
4 2 5
-3 0 2
7 -9 -3
4 4 -6
8 -1 8
1 2
2 3
2 1000
2 100
3 1000
3 100
4 1000
0.0287058122
0.2874671888
0.1120998619
1.1272896971
impossible