GRAD

도로망은 좌표 평면 위의 도시와, 두 도시를 잇는 직선 도로로 구성된다. 도로는 교차할 수 있지만, 다른 도로로 바꿔 탈 수 있는 곳은 그 도로가 연결한 두 도시뿐이다. 도로 길이는 두 도시 사이의 유클리드 거리다.

처음에는 도시 1과 2만 있고 서로 도로로 연결된다. 이후 각 단계에서 새 도시가 하나 추가되며, 그 순간 서로 도로로 직접 연결된 두 기존 도시 A, B와 각각 새 도로로 연결된다.

명령을 처리하는 프로그램을 작성한다.

• d X Y A B: 좌표 $(X,Y)$에 새 도시를 추가하고, 그 순간 도로로 직접 연결된 A와 B에도 각각 도로로 연결한다.
• u A B: 두 도시 사이 최단 도로 거리를 출력한다.

도시 1, 2의 좌표와 명령 수 $N$이 주어진다. 각 명령은 d 또는 u 형식이다. 같은 좌표의 도시는 없다.

각 u 명령에 대해 거리를 한 줄에 출력한다. 공식 정답과의 절대 오차는 $0.1$ 이하여야 한다.