사막 여행

당신은 사막에 갇혀 있다. 사막은 직교 좌표 평면으로 생각할 수 있다. 사막에는 여러 오아시스가 있고, 각 오아시스의 $x$좌표와 $y$좌표를 알고 있다. 당신은 오아시스 쌍 사이를 오가는 여러 번의 여행을 할 것이다. 각 여행에는 출발 오아시스와 도착 오아시스가 정해져 있다. 어떤 여행이든 가는 도중에 다른 오아시스에 얼마든지 들를 수 있다.

사막을 이동하려면 물이 필요하다. 사막에서는 거리 $1$을 이동할 때마다 물 $1$이 필요하다. 각 여행에서 사용할 물통의 크기를 정해야 한다. 필요한 양보다 큰 물통을 들고 다닐 이유가 없으므로, 각 여행에는 필요한 최소 크기의 물통을 사용하려고 한다.

여행 중 들르는 각 오아시스에서 물통을 다시 채워 다음 오아시스까지 버틸 수 있다. 따라서 그 여행의 경로에서 연속한 두 오아시스 사이의 유클리드 거리의 최댓값이 필요한 물통의 크기를 결정한다. 예를 들어 $(0,0)$에서 $(2,4)$를 거쳐 $(4,5)$로 이동했다면 최대 거리는 $(0,0)$과 $(2,4)$ 사이의 거리인 약 $4.472$이다. 이 거리가 $(2,4)$와 $(4,5)$ 사이의 거리보다 크기 때문이다. 이 값이 그 여행에 필요한 물통의 크기를 결정한다.

오아시스의 수와 여러 여행이 주어진다. 각 여행에는 출발 오아시스와 도착 오아시스가 정해져 있다. 각 여행에서 연속한 두 오아시스 사이의 유클리드 거리의 최댓값이 최소가 되도록 경로를 정하고, 그 최솟값을 구하여라.

첫째 줄에는 오아시스의 수 $O$가 주어진다. ($1 \le O \le 5000$)

다음 $O$개 줄 중 $i$번째 줄에는 $i$번째 오아시스의 좌표 $x_i$와 $y_i$가 주어진다. ($-10^6 \le x_i \le 10^6$, $-10^6 \le y_i \le 10^6$)

오아시스에는 $1$부터 $O$까지의 번호가 붙어 있다.

그다음 줄에는 여행의 수 $Q$가 주어진다. ($1 \le Q \le 500000$)

다음 $Q$개 줄 중 $i$번째 줄에는 $i$번째 여행의 출발 오아시스 번호 $s_i$와 도착 오아시스 번호 $e_i$가 주어진다. ($1 \le s_i \le O$, $1 \le e_i \le O$)

각 여행마다 한 줄에 하나씩, 그 여행에 필요한 물통 크기의 최솟값을 출력한다. 이 값은 $s_i$번 오아시스에서 $e_i$번 오아시스로 가는 경로를 적절히 정했을 때, 그 경로에서 연속한 두 오아시스 사이의 유클리드 거리의 최댓값으로 가능한 최솟값이다. 정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정된다.