Two agents A and B, known as a great combination, are conducting the infiltration mission to a secret base.
Due to the strict security of the base, two agents have decided to follow the prechecked safe infiltration routes R_{A} and R_{B}, respectively.
Each infiltration route is a twodimensional polyline, a series of line segments.
Each of the agents starts at the starting end of the first segment of the corresponding route. The mission is over when both agents are on the finishing ends of the last segments of their routes simultaneously.
During the mission, each of the agents can move forward or backward at an arbitrary speed, or stop for a moment, as long as the movements along the route are continuous, but cannot jump changing the position abruptly.
Although segments of a route may have crosses or overlaps with one another, they cannot be used for movements.
Precisely, an agent on one segment can transfer to another segment only in the following cases.
 The destination segment is the next segment on the route, and the agent is on the finishing end of the current segment.
 The destination segment is the previous segment on the route, and the agent is on the starting end of the current segment.
For example, in Figure G1 below,
the agent must move to the finishing end of the segment 34 of
R_{B}, (−1, 1), in order to transfer to the segment 45.
Although, the agent passes the same point as the finishing end
of the last segment, (2, 1), when the agent transfers from the
segment 23 to the segment 34, the agent is not considered to be on
the finishing end of the last segment at that time.
Figure G1: Infiltration routes for the first dataset of Sample Input
Figure G2: Infiltration routes for the second dataset of Sample Input
To prepare for the contingency, the agents carry radio communicators and they should always be within the range allowing communication between them.
Stronger wave enables longer communication distance, but increases the interception possibilities.
Give the minimum required communication distance to accomplish the mission with appropriate movements of the agents.
Input
The input consists of multiple datasets, each in the following format.
n
x_{A,1} y_{A,1}
⋮
x_{A,n} y_{A,n}
m
x_{B,1} y_{B,1}
⋮
x_{B,m} y_{B,m}
n is the number of the vertices of the infiltration route R_{A}.
n is an integer between 2 and 40, inclusive.
x_{A,i} and y_{A,i} (1 ≤ i ≤ n) are the coordinates of the ith vertex.
x_{A,i} and y_{A,i} are integers satisfying −1000 ≤ x_{A,i} ≤ 1000 and −1000 ≤ y_{A,i} ≤ 1000, respectively.
For 1 ≤ i ≤ n−1,
(x_{A,i}, y_{A,i}) is the starting end of the ith line segment, and (x_{A,i+1}, y_{A,i+1}) is its finishing end.
All line segments have nonzero lengths.
That is, x_{A,i} ≠ x_{A,i+1} and/or y_{A,i} ≠ y_{A,i+1} holds.
m and the value pairs of x_{B,j} and y_{B,j} (1 ≤ j ≤ m) represent the infiltration route R_{B}. The format and the constraints are the same as those for R_{A}.
The end of the input is indicated by a line containing a zero.
The number of datasets does not exceed 50.
Output
For each dataset, output in a line the maximum distance between the two agents during the mission when they move in a way that minimizes the maximum distance.
The error contained in the output should not exceed 10^{−8}. The output shall be deemed correct if its relative error or its absolute error is within this limit.
Sample Input
2
0 0
2 0
5
0 1
2 1
2 1
1 1
2 1
4
0 0
4 6
0 3
8 6
3
0 0
4 3
8 6
10
40 15
40 20
40 15
45 10
50 12
50 10
50 15
60 15
65 20
70 18
10
40 10
40 15
45 20
50 18
50 15
50 20
60 20
60 15
65 10
70 12
0
Output for the Sample Input
1.414213562373
2.400000000000
9.284766908853
Problem H
Artist in Agony
You, an artist, prepared a sufficient number of balls and also strings to link them for your artwork. Balls are to be given sequential numbers eventually, but only one of the balls is given number 1 at the beginning. No other balls are numbered and no balls are linked to any other balls yet.
An artwork is created by carrying out either of the following actions repetitively.
 Replication:
 The work in progress is replicated. Let n be the number of balls numbered so far. You pick n unnumbered balls and number them n+1, ..., 2n. This results in 2n balls uniquely numbered 1 through 2n. Then for all pairs of balls linked directly before replication numbered u and v, the two balls newly numbered n+u and n+v are linked with a string.
 Making a new link:
 Two distinct balls already numbered are chosen and linked with a string. When two balls are already linked directly, this action does nothing.
Note that, as initially only one ball is numbered, you have to start with the replication action.
Figure H1 shows the process of artwork creation of the second dataset in Sample Input.
Figure H1: Artwork creation example
Being a perfectionist as with all the real artists, you cannot stand imperfect works. When you find a work unsatisfactory, you have to destroy it completely as quick as possible by tearing off all the links in it. You grab some of the numbered balls in one hand, the rest in the other hand, and pull them apart tearing off all the strings linking the balls in your right hand and the balls in your left hand. If all the strings linking the balls are torn off by doing this operation just once, your destruction is successful. Conversely, any remaining links between two balls in one hand mean that the destruction is a failure.
Figure H2 shows the work of the second dataset in Sample Input being destroyed. To destroy the work, you have to grab three or more balls in each of your hands.
Figure H2: Destructing the artwork described above
Given the sequence of actions that created the work, judge whether you can destroy it in the way described above. If you can, find the minimum number of balls you have to grab in your left hand. You may grab an arbitrary number of balls in your right hand.
Input
The input consists of multiple datasets, each in the following format.
m
a_{1}
⋮
a_{m}
m is the number of actions you have carried out. m is a positive integer and does not exceed 300.
The ith action a_{i} (i = 1, ..., m) is given by either of the following forms.
COPY

This represents the Replication action in the problem statement. It is guaranteed that each dataset contains no more than 60
COPY
actions.
LINK
u v

This represents the Making a new link action in the problem statement. In this action, the two balls numbered u and v were inspected, and a new link between them was made if they had not been directly connected yet. u and v are positive integers that satisfy u < v. It is guaranteed that two balls had already been numbered u and v at that time.
The end of the input is indicated by a line containing a zero. The number of datasets does not exceed 100.
Output
For each of the datasets, output one line containing an integer. If you can destroy the work in the way described above, output the minimum number of balls you need to grab in your left hand. Otherwise, output −1.
Sample Input
3
COPY
LINK 1 2
COPY
8
COPY
COPY
LINK 1 2
LINK 1 3
LINK 1 3
COPY
LINK 5 6
LINK 3 6
5
COPY
LINK 1 2
COPY
LINK 1 3
LINK 2 3
2
COPY
COPY
0
Output for the Sample Input