필수 고가도로 timer 20s memory 2048MB

에키야(Ekiya)의 마을에 세워진 현대적인 철도 시스템이 큰 난관에 부딪혔다: 남북 방향으로 뻗은 주요 고속도로이다. 고속도로 서쪽에는 이미 \mathbf{W}개의 역이 건설되어 서로 연결되어 있고, 동쪽에는 \mathbf{E}개의 역이 건설되어 연결되어 있다. 서쪽의 한 역과 동쪽의 한 역을 잇는 연결이 하나 더 필요하지만, 고속도로가 가로막고 있으므로 그 연결은 고가도로(overpass)를 이용해 건설해야 한다.

에키야는 고가도로로 어떤 역들을 연결하는 것이 가장 편리할지 평가하고 있다. 그 평가의 일환으로, 가능한 각 선택지마다 시스템 안에서의 경로의 평균 길이(지나는 역의 수 기준)가 어떻게 달라지는지 알고 싶다.

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

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

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

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

현재 역들과 기존 연결, 그리고 고가도로 연결의 선택지 목록이 주어질 때, 각 선택지를 유일한 고가도로로 추가했을 경우 만들어지는 지도의 평균 거리를 계산하여 에키야를 도와주자.