언터웨이브 거리

2312년, 인류의 별을 향한 질주는 이제 200년이 되었다. 항성계 사이의 실시간 통신 문제는 여전히 남아 있고, 그 해법이 언터웨이브(UW)다.

UW 통신은 다음과 같이 동작한다. 일부 항성계 쌍 사이에는 직접 UW 링크가 설치되어 있다. 직접 링크가 없는 두 항성계는 기존 링크를 따라 중간 항성계를 거쳐 건너며 통신한다. 어떤 항성계도 직접 링크가 20개를 넘지 않지만, 모든 항성계 쌍은 직접 또는 간접적으로 통신할 수 있다.

회사는 새 본부를 두 항성계에 세워야 한다. 하나는 인류 항성계, 다른 하나는 외계 항성계다. 통신 지연의 척도인 UW 거리가 최소가 되도록 두 항성계를 고른다.

각 항성계에는 UW 통신에 영향을 주는 중력값이 있다. 두 항성계가 같은 중력값을 갖는 일은 없다. 통신 경로가 출발지와 도착지를 포함해 중력값 수열 $G = g_1, g_2, \ldots, g_n$을 지난다고 하자. 그러면 길이가 $n-1$인 수열 세 개를 정의한다.

$\operatorname{cap}(G) = g_2+g_1,\ g_3+g_2,\ \ldots,\ g_n+g_{n-1} \quad \text{(커패시턴스)}$

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

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

길이가 같은 수열 $A=a_1, \ldots, a_m$과 $B=b_1, \ldots, b_m$에 대해 $A\cdot B$와 $A-B$는 원소별 곱과 차를 뜻한다.

UW 거리는 다음 수열 원소들의 합의 절댓값이다.

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

UW 거리는 매우 클 수 있다. 다행히 회사에는 중력 분산 장치가 있다. 이 장치는 항성계 하나에 놓을 수 있고, 놓인 자리에 계속 머문다. 장치가 놓인 항성계의 중력은 1 줄고, 그 항성계와 직접 링크된 모든 항성계의 중력은 1 늘어난다. 장치 사용은 선택 사항이다.

첫 줄에 항성계의 수 $n$ ($2 \leq n \leq 50\,000$)이 주어진다. 다음 $n$개 줄은 1번부터 $n$번까지 항성계를 g d 형식으로 설명한다. $g$는 중력값 ($1 \leq g \leq 1\,000\,000$)이고, $d$는 인류 항성계이면 h, 외계 항성계이면 a다. 각 종류의 항성계는 적어도 하나 있으며, 모든 $g$는 서로 다르다.

다음 줄에는 직접 링크의 수 $e$가 양의 정수로 주어진다. 이어지는 $e$개 줄에는 직접 링크된 두 항성계의 번호가 공백으로 구분되어 주어진다. 링크는 양방향이고, 같은 링크는 한 번만 나타난다. 어떤 항성계도 직접 링크되는 항성계가 20개를 넘지 않는다.

인류 항성계와 외계 항성계의 쌍에서 달성할 수 있는 UW 거리의 최솟값을 출력한다.