Unterwave Distance

The year is 2312, and humanity's rush to the stars is now 200 years old. Real-time communication between star systems is still an open problem, and the answer is the unterwave.

Unterwave (UW) communication works as follows. Direct UW links exist between certain pairs of star systems. Two systems without a direct link communicate by hopping along existing links through intermediate systems. No system has more than 20 direct links, but any two systems can communicate, directly or indirectly.

Your company must choose two star systems for its new home offices: one in a human system and one in an alien system. Choose them so that the UW distance, a measure of communication latency, is minimized.

Every star system has a gravity value that affects UW communication. No two star systems have the same gravity. Suppose a communication path passes through the sequence $G = g_1, g_2, \ldots, g_n$ of gravity values, including its source and destination. Then three sequences of $n-1$ terms are defined.

$\operatorname{cap}(G) = g_2+g_1,\ g_3+g_2,\ \ldots,\ g_n+g_{n-1} \quad \text{(Capacitance)}$

$\operatorname{pot}(G) = g_2-g_1,\ g_3-g_2,\ \ldots,\ g_n-g_{n-1} \quad \text{(Potential)}$

$\operatorname{ind}(G) = g_2\cdot g_1,\ g_3\cdot g_2,\ \ldots,\ g_n\cdot g_{n-1} \quad \text{(Inductance)}$

For sequences $A=a_1, \ldots, a_m$ and $B=b_1, \ldots, b_m$, $A\cdot B$ and $A-B$ denote the termwise product and difference.

The UW distance is the absolute value of the sum of the terms of

$\operatorname{pot}(G)\cdot\left(\left[\operatorname{cap}(G)\cdot\operatorname{cap}(G)\right]-\operatorname{ind}(G)\right)$

The UW distance can be quite large. Fortunately, your company has a gravity dispersal device. It may be placed in any single system, where it stays. It reduces that system's gravity by 1 and increases by 1 the gravity of every system directly linked to it. Using the device is optional.

The first line has one integer $n$ ($2 \leq n \leq 50\,000$), the number of star systems. The next $n$ lines describe systems 1 to $n$ in the form g d. Here $g$ is the gravity value ($1 \leq g \leq 1\,000\,000$), and $d$ is h for a human system or a for an alien system. There is at least one system of each type, and all values of $g$ are distinct.

The next line has one positive integer $e$, the number of direct links. Each of the next $e$ lines contains two system numbers separated by a space, meaning those systems are directly linked. Links are bidirectional, and no link appears more than once. No system links directly to more than 20 other systems.

Output the minimum UW distance that can be achieved between an alien system and a human system.