프로거

개구리 Freddy는 호수 한가운데의 돌 위에 앉아 있다. 문득 그는 또 다른 돌 위에 앉아 있는 개구리 Fiona를 발견하고 그녀에게 가기로 마음먹는다. 하지만 물이 더럽고 관광객이 바른 자외선 차단제로 뒤덮여 있어, 그는 헤엄치는 대신 돌에서 돌로 점프해서 가려고 한다.

안타깝게도 Fiona의 돌은 한 번의 점프로 닿기에는 너무 멀리 있다. 그래서 Freddy는 중간에 있는 다른 돌들을 여러 번 거쳐서 그녀에게 가기로 한다.

어떤 경로를 따라 순서대로 점프하려면, 개구리의 점프 능력(한 번에 뛸 수 있는 최대 거리)은 그 경로에서 가장 긴 한 번의 점프 길이 이상이어야 한다.

두 돌 사이의 개구리 거리(frog distance)는 다음과 같이 정의한다. 한 돌에서 다른 돌로 가는 모든 가능한 경로에 대해, 그 경로에서 가장 긴 점프의 길이를 그 경로의 비용이라고 하자. 개구리 거리는 이 비용의 모든 경로에 대한 최솟값이다.

Freddy의 돌, Fiona의 돌, 그리고 호수에 있는 나머지 돌들의 좌표가 주어진다. Freddy의 돌과 Fiona의 돌 사이의 개구리 거리를 구하여라.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 번째 줄에는 돌의 개수 $n$이 주어진다. 이어지는 $n$개의 줄에는 각 돌의 좌표를 나타내는 두 정수 $x_i$와 $y_i$가 주어진다. 돌 #1은 Freddy의 돌, 돌 #2는 Fiona의 돌이며, 나머지 $n-2$개의 돌은 빈 돌이다. 각 테스트 케이스 사이에는 빈 줄이 하나씩 있다. $n$이 $0$이면 입력이 끝난다.

각 테스트 케이스마다 두 줄을 출력한다. 첫 줄에는 Scenario #x를, 둘째 줄에는 Frog Distance = y를 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 개구리 거리를 소수점 셋째 자리까지 반올림한 값이다. 연속한 두 테스트 케이스의 출력 사이에는 빈 줄을 하나씩 넣는다.