두 왕국 잇기

놀고니아 왕국과 콰드라도니아 왕국은 오랫동안 참혹한 전쟁을 벌였다. 이제는 아무도 전쟁이 왜 시작되었는지 기억하지 못하기 때문에, 역사가들은 이 전쟁을 거의 완전히 무의미한 전쟁(Almost Completely Meaningless, ACM)이라고 부른다. ACM 전쟁이 끝나자 두 왕국은 다시 피를 흘리지 않으려고 관계를 다지기로 했고, 국제 분쟁 예방 협의회(International Consortium for the Prevention of Conflicts, ICPC)에 자문을 구했다. ICPC는 놀고니아의 도시 하나와 콰드라도니아의 도시 하나를 잇는 도로를 딱 하나만 새로 놓아서 두 나라가 교역하고 문화를 주고받게 하라고 권고했다.

놀고니아에는 도시가 $N$개, 콰드라도니아에는 도시가 $Q$개 있다. 한 왕국의 도로망은 그 왕국의 서로 다른 두 도시를 잇는 양방향 도로의 집합이고, 같은 왕국의 어느 도시에서 다른 어느 도시로 가는 경로, 즉 연속된 도로의 나열이 정확히 하나 존재한다. 이런 도로망의 크기는 두 도시 사이를 오갈 때 지나야 하는 도로 수의 최댓값으로 정의한다.

ICPC가 두 왕국을 잇는 새 도로의 양 끝 도시를 지정하지 않았으므로, 주민들은 합쳐진 도로망의 크기가 너무 커지지 않을까 걱정하고 있다. 두 번째 ACM 전쟁을 막으려면 그렇지 않다는 것을 보여야 한다. 두 왕국 사이에 놓을 수 있는 모든 도로가 같은 확률로 선택된다고 할 때, 완성된 도로망 크기의 기댓값을 구하라.

첫째 줄에 두 왕국의 도시 수를 나타내는 정수 $N$과 $Q$가 주어진다 ($1 \le N, Q \le 4 \times 10^4$). 놀고니아의 도시는 $1$부터 $N$까지, 콰드라도니아의 도시는 $1$부터 $Q$까지 서로 다른 정수로 구분한다.

이어지는 $N - 1$개 줄에는 놀고니아의 도로가 한 줄에 하나씩 주어진다. 각 줄의 서로 다른 정수 $A$와 $B$는 도시 $A$와 도시 $B$를 잇는 도로를 뜻한다 ($1 \le A, B \le N$).

그다음 $Q - 1$개 줄에는 콰드라도니아의 도로가 같은 형식으로 주어진다. 각 줄의 서로 다른 정수 $C$와 $D$는 도시 $C$와 도시 $D$를 잇는 도로를 뜻한다 ($1 \le C, D \le Q$).

각 왕국의 도로망에서 두 도시 사이의 경로는 항상 정확히 하나다.

두 왕국을 잇는 도로가 놓일 수 있는 모든 자리가 같은 확률이라고 할 때, 합쳐진 도로망 크기의 기댓값을 한 줄에 출력한다.

소수점 아래 셋째 자리까지 출력하고, 그보다 아래 자리는 반올림한다. 정확히 절반인 값은 큰 쪽으로 올린다. 기댓값이 정수여도 소수점 아래 세 자리를 모두 적는다.