필수적인 고가교

Ekiya의 마을에 건설된 현대식 철도 시스템은 큰 장애물에 부딪혔다. 바로 남북으로 뻗은 주요 고속도로이다. 고속도로 서쪽에는 이미 $\mathbf{W}$개의 역이 건설되어 연결되어 있고, 동쪽에는 $\mathbf{E}$개의 역이 건설되어 연결되어 있다. 서쪽 역과 동쪽 역 사이에 연결 하나가 더 필요하지만, 고속도로가 가로막고 있으므로 그 연결은 고가교를 이용해 건설해야 한다.

Ekiya는 고가교로 어느 역들을 연결하는 것이 가장 편리할지 평가하고 있다. 이 평가의 일환으로, 가능한 각 선택지에 따라 시스템 내 경로의 평균 길이(역의 개수 기준)가 어떻게 달라질 수 있는지 알고 싶어 한다.

역 $s$와 $t$ 사이의 경로는 $s$에서 시작하여 $t$에서 끝나는 서로 다른 역들의 목록이며, 목록에서 연속한 임의의 두 역은 연결을 공유한다. 현재 철도 시스템에는 서쪽에 $\mathbf{W}$개의 역이 있고, 이들은 서로 다른 임의의 두 서쪽 역 사이에 정확히 하나의 경로가 있도록 $\mathbf{W}-1$개의 연결로 이어져 있다. 마찬가지로 동쪽에는 $\mathbf{E}$개의 역이 있고, 이들은 서로 다른 임의의 두 동쪽 역 사이에 정확히 하나의 경로가 있도록 $\mathbf{E}-1$개의 연결로 이어져 있다. 서쪽 역 하나와 동쪽 역 하나를 잇는 고가교 연결이 건설되면, 서로 다른 임의의 두 역 사이에는 정확히 하나의 경로가 존재하게 된다.

완전한 지도란 총 $\mathbf{W}+\mathbf{E}-1$개의 연결을 가지며 임의의 역 쌍 사이에 정확히 하나의 경로가 있는 지도이다. 완전한 지도의 평균 거리는 서로 다른 모든 역 쌍 사이 경로 길이의 평균이다. 경로의 길이는 그 경로를 정의하는 역 목록의 길이보다 하나 작다(예를 들어, 직접 연결된 역 사이 경로의 길이는 $1$이다).

예시로, 아래 그림은 서쪽에 $\mathbf{W} = 2$개의 역이 있고 동쪽에 $\mathbf{E} = 3$개의 역이 있는 상황을 보여 준다. 가능한 $2$개의 고가교가 표시되어 있다.

이 표는 각 고가교를 건설했을 때 역 쌍 사이 경로의 길이를 보여 준다.

현재의 역과 연결 및 고가교 연결의 선택지 목록이 주어질 때, 해당 선택지의 고가교 연결만 건설했을 경우 만들어지는 지도의 평균 거리를 계산하여 Ekiya를 도와라.

제한

메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. $2 \le \mathbf{W} \le 10^5$. $2 \le \mathbf{E} \le 10^5$. 모든 $i$에 대해 $i + 1 \le \mathbf{X_i} \le \mathbf{W}$. (이는 각 서쪽 역 쌍 사이에 정확히 하나의 경로가 있음을 의미한다.) 모든 $j$에 대해 $j + 1 \le \mathbf{F_j} \le \mathbf{E}$. (이는 각 동쪽 역 쌍 사이에 정확히 하나의 경로가 있음을 의미한다.) 모든 $k$에 대해 $1 \le \mathbf{A_k} \le \mathbf{W}$. 모든 $k$에 대해 $1 \le \mathbf{B_k} \le \mathbf{E}$. 모든 $k \neq \ell$에 대해 $(\mathbf{A_k}, \mathbf{B_k}) \neq (\mathbf{A_\ell}, \mathbf{B_\ell})$. (나열된 각 고가교 연결은 서로 다르다.)

테스트 세트 1 (Visible Verdict)

시간 제한: 20초. $1 \le \mathbf{C} \le 2$.

테스트 세트 2 (Hidden Verdict)

시간 제한: 40초. $1 \le \mathbf{C} \le 10^5$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 $\mathbf{W}$, $\mathbf{E}$, $\mathbf{C}$가 있는 줄로 시작하며, 각각 서쪽 역의 수, 동쪽 역의 수, 고가교 연결 선택지의 수를 나타낸다. 서쪽 역에는 $1$부터 $\mathbf{W}$까지 번호가 매겨지고, 동쪽 연결에는 $1$부터 $\mathbf{E}$까지 번호가 매겨진다.

테스트 케이스의 두 번째 줄에는 $\mathbf{W}-1$개의 정수 $\mathbf{X_1}, \mathbf{X_2}, \dots, \mathbf{X_{W-1}}$가 주어지며, 이는 서쪽 역 사이의 기존 연결 중 $i$번째 연결이 서쪽 역 $i$와 $\mathbf{X_i}$를 잇는다는 것을 나타낸다.

테스트 케이스의 세 번째 줄에는 $\mathbf{E}-1$개의 정수 $\mathbf{F_1}, \mathbf{F_2}, \dots, \mathbf{F_{E-1}}$가 주어지며, 이는 동쪽 역 사이의 기존 연결 중 $j$번째 연결이 동쪽 역 $j$와 $\mathbf{F_j}$를 잇는다는 것을 나타낸다.

마지막으로, 테스트 케이스의 마지막 $\mathbf{C}$개 줄은 고가교 연결의 선택지를 설명한다. 이 줄들 중 $k$번째 줄에는 두 정수 $\mathbf{A_k}$와 $\mathbf{B_k}$가 주어지며, 각각 고가교 연결의 $k$번째 선택지가 연결할 서쪽 역과 동쪽 역을 나타낸다.

각 테스트 케이스마다 Case #$x$: $y_1 ~ y_2 ~ \cdots ~ y_{\mathbf{C}}$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y_k$는 모든 기존 연결에 $k$번째 선택지를 고가교 연결로 추가하여 만들어지는 지도의 평균 거리이다.

$y_1$, $y_2$, $\dots$, $y_k$은 정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참고하라.

예제 케이스 #1은 문제 설명에서 설명하고 그림으로 나타냈다. 예제 케이스 #2와 예제 케이스 #3은 아래에 그림으로 나타냈다.