멋쟁이 개구리

해마다 열리는 연못 건너기 대회는 개구리의 속도와 폼을 함께 본다. 개구리는 연잎에서 연잎으로 뛰어 연못을 건넌다. 한 번 뛰는 데 걸리는 시간은 거리와 상관없이 같아서, 속도를 올리려면 뛰는 횟수를 줄여야 한다. 폼은 멀리 뛰는 데서 나온다. 훈련받은 대회용 개구리가 짧게 깡충거리는 모습만큼 볼품없는 것이 없어서, 심판은 뛰는 횟수가 가장 적은 경로 가운데 가장 짧은 도약이 최대한 긴 경로를 높게 친다.

지난해 우승자 프레도는 연잎 배치도와 개구리가 뛸 수 있는 최대 거리를 읽어 가장 좋은 경로의 성적을 알려 주는 프로그램을 원한다.

경로는 뛰는 횟수가 적을수록 좋다. 세 번 뛰는 경로는 네 번 뛰는 경로보다 무조건 좋다. 뛰는 횟수가 가장 적은 경로가 여럿이면 그중 가장 짧은 도약이 가장 긴 경로가 최선이다.

위 그림은 첫 번째 예제의 배치다. 0번 연잎이 출발점, 1번 연잎이 도착점이다. 0, 2, 3, 1 경로는 뛰는 횟수가 가장 적지만 2번에서 3번으로 가는 도약이 유난히 짧다. 이 배치에서 가장 좋은 경로는 0, 4, 7, 1이다.

입력은 여러 개의 연못으로 이루어진다. 각 연못의 첫 줄에는 연잎의 개수 $P$와 개구리가 뛸 수 있는 최대 거리 $D$가 정수로 주어진다. 이어지는 $P$개의 줄에는 연잎 중심의 좌표 $X$와 $Y$가 실수로 하나씩 주어지며, 0번 연잎부터 번호 순서대로 나온다. 모든 도약은 중심에서 중심으로 이루어지고, 중심을 벗어나 뛰거나 내려앉은 개구리는 즉시 실격이다.

각 연못에서 0번 연잎이 출발점이고 1번 연잎이 도착점이다.

두 연잎 중심 사이의 거리가 $D$ 이하이면 그 도약은 유효하다. 거리가 정확히 $D$인 도약도 유효하다.

$P$와 $D$ 자리에 0 0이 적힌 줄이 나오면 입력이 끝난다. 그 줄은 연못이 아니다.

제한

• $2 \le P \le 200$
• $0 < D < 1000$
• $0 < X < 1000$, $0 < Y < 1000$
• 연못은 최대 20개다.
• 1번 연잎은 언제나 0번 연잎에서 유효한 도약만 밟아 갈 수 있다.

연못마다 한 줄에 가장 좋은 경로의 도약 횟수와 그 경로에서 가장 짧은 도약의 길이를 공백 하나로 구분해 출력한다. 길이는 소수점 아래 한 자리로 반올림한다.

가장 좋은 경로가 여럿이어도 두 값은 모두 같으므로 답은 하나로 정해진다. 최적값이 반올림 경계에 걸려 마지막 자리가 흔들리는 입력은 없다.