Simulate City Network Construction and Shortest Path Queries

You are given a set of cities located in a 2D coordinate system. Initially, there are two cities (city 1 and city 2) that are connected by a bidirectional road. The road between any two cities has a weight equal to their Euclidean distance.

You need to simulate the city network construction process with two types of operations:

• d X Y A B: Add a new city at coordinate \((X,Y)\). It is guaranteed that no city exists at \((X,Y)\). The newly added city will be assigned the next available natural number as its label. Establish bidirectional roads between the new city and the cities with labels A and B. The weight of each new road is the Euclidean distance between the corresponding cities.
• u A B: Query the shortest path distance between city A and city B in the current network.

Note: For any two cities with coordinates \((x_1,y_1)\) and \((x_2,y_2)\), the road length is given by \[ d = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2} \] (in \(\LaTeX\) format). It is guaranteed that after every addition, the network remains connected.

inputFormat

The input begins with the coordinates of the two initial cities:

1. Line 1: Two space-separated numbers \(X_1\) and \(Y_1\) representing the coordinates of city 1.
2. Line 2: Two space-separated numbers \(X_2\) and \(Y_2\) representing the coordinates of city 2.

Line 3 contains an integer \(Q\) representing the number of operations.

The following \(Q\) lines each represent an operation in one of the following formats:

• d X Y A B — add a new city at \((X,Y)\) and connect it with cities A and B.
• u A B — query the shortest path distance from city A to city B.

outputFormat

For each query operation (lines beginning with u), output a line with the shortest path distance from city A to city B. The answer should be printed with 6 decimal places.

sample

0 0
3 4
3
d 6 8 1 2
u 3 2
u 1 3

5.000000
10.000000