은하 퀘스트

당신은 우주선을 타고 은하를 여행하고 있다. 은하에는 1번부터 $n$번까지 번호가 붙은 행성이 $n$개 있으며, 각 행성은 3차원 공간의 점으로 나타낸다.

행성들 사이는 $m$개의 우주 고속도로를 따라 이동할 수 있다. 각 고속도로는 연결된 두 행성을 잇는 직선을 따라 놓여 있다. 엔진은 $1\text{m/s}^2$의 가속도로 가속하거나 감속할 수 있으며, 이때 초당 1리터의 연료를 쓴다. 속도에는 제한이 없지만, 고속도로의 끝 행성에 도착할 때마다 반드시 완전히 멈춰야 한다.

고속도로는 연결된 두 행성 이외의 행성을 지나갈 수 있다. 하이퍼스페이스 기술 덕분에 우주선은 그런 행성을 멈추지 않고 그대로 통과한다. 다만 고속도로 도중에 다른 고속도로로 갈아탈 수는 없으므로, 고속도로는 항상 처음부터 끝까지 전부 달려야 한다.

그림 G.1: 첫 번째 입력의 그림이다. 고속도로는 파란색으로, 1번 행성에서 3번 행성까지의 경로가 표시되어 있다. 고속도로 시작점의 초록색은 가속을, 끝점의 빨간색은 감속을 뜻한다. 그림은 두 번째 임무의 최적 경로를 보여준다.

여러 임무를 수행해야 한다. 각 임무에서 우주선은 집 행성(1번)에서 출발하여 주어진 제한 시간 안에 목표 행성에 도달해야 한다. 각 임무마다 완료할 수 있는지 판단하고, 완료할 수 있다면 필요한 연료의 최솟값을 구한다.

첫 줄에 세 정수 $n$, $m$, $q$가 주어진다 ($1 \le n,m,q \le 10^5$, $n \ge 2$). $n$은 행성의 수, $m$은 고속도로의 수, $q$는 임무의 수이다.

다음 $n$개의 줄에는 행성 $i$의 좌표 $x_i$, $y_i$, $z_i$가 미터 단위로 주어진다 ($|x_i|,|y_i|,|z_i| \le 10^3$, $1 \le i \le n$).

다음 $m$개의 줄에는 고속도로가 잇는 두 행성 $a$, $b$가 주어진다 ($1 \le a,b \le n$, $a \neq b$). 고속도로는 양방향으로 이동할 수 있다.

마지막 $q$개의 줄에는 임무의 목표 행성 $c$와 제한 시간 $t$가 초 단위로 주어진다 ($2 \le c \le n$, $1 \le t \le 10^3$).

행성의 위치는 모두 서로 다르다. 같은 두 행성을 잇는 고속도로는 없다. 각 임무에서 제한 시간과 최단 완료 시간의 차이는 절대값과 상대값 모두 $10^{-6}$ 이상이다.

각 임무마다 목표 행성에 제한 시간 안에 도달하는 데 필요한 연료의 최솟값을 리터 단위로 출력한다. 제한 시간 안에 도달할 수 없으면 impossible을 출력한다. 답은 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 맞는 것으로 본다.