서버 이전

마이클은 수백 개의 병렬 프로세서와 수 테라바이트의 주 기억장치 및 디스크 공간을 갖춘 강력한 컴퓨터 서버를 가지고 있다. 이 서버에서는 중요한 계산이 끊임없이 실행되고 있어, 전원이 한순간도 끊기지 않고 공급되어야 한다.

새로 구입한 서버들을 들여놓기 위해 마이클의 서버를 옮겨야 한다. 다행히 이 서버에는 이중화된 전원 공급 장치가 두 개 있어서, 두 전원 코드 중 적어도 하나가 콘센트에 연결되어 있는 한 서버는 계속 동작할 수 있다. 서버가 어떤 콘센트에 연결되어 있으면, 그 콘센트로부터 연결에 사용한 코드의 길이보다 멀지 않은 임의의 위치로 서버를 옮길 수 있다.

서버가 처음에 연결된 콘센트와 마지막에 연결될 콘센트, 그리고 서버실에 있는 콘센트들의 위치가 주어진다. 서버를 항상 켜진 상태로 유지하면서 목표 콘센트로 옮기기 위해 코드를 콘센트에 꽂아야 하는 최소 횟수를 구하여라. 처음 상태와 마지막 상태에서는 오직 하나의 코드만 콘센트에 연결되어 있다.

입력의 첫 줄에는 처리할 테스트 케이스의 수가 정수로 주어진다. 각 테스트 케이스의 첫 줄은 다음 형식이다.

OUTLETS OUTLET_INITIAL OUTLET_FINAL LENGTH1 LENGTH2

• OUTLETS: 서버실에 있는 콘센트의 개수 ($2 \le \text{OUTLETS} \le 1000$).
• OUTLET_INITIAL: 서버가 처음에 연결된 콘센트의 번호(1부터 시작).
• OUTLET_FINAL: 서버가 마지막에 연결될 콘센트의 번호(1부터 시작).
• LENGTH1, LENGTH2: 두 전원 코드의 길이로, 소수점 아래 최대 세 자리까지 주어지는 양수이다 ($0 < \text{LENGTH1}, \text{LENGTH2} \le 30000$).

그 다음에는 콘센트의 정수 좌표가 한 줄에 하나씩 OUTLETS개 주어지며, $k$번째 줄은 $k$번째 콘센트의 위치를 나타낸다. 각 좌표는 공백으로 구분된 두 정수($x$좌표와 $y$좌표)로 주어지고, 절댓값은 최대 30000이다. 모든 좌표는 서로 다르며, 처음 콘센트와 마지막 콘센트도 서로 다르다.

각 테스트 케이스마다, 서버를 항상 켜진 상태로 유지하면서 목표 콘센트로 옮기기 위해 코드를 콘센트에 꽂아야 하는 최소 횟수를 출력한다. 옮기는 것이 불가능하면 Impossible을 출력한다.