시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 1024 MB224743.150%

문제

레이무가 사는 환상향에는 $N$ 개의 신사가 있습니다. 이 중 $K$ 개의 신사는 명신을 모시는 명신대사입니다. 두 신사를 양방향으로 잇는 길이 $N-1$ 개 있고, 임의의 두 신사를 한 개 이상의 길을 사용해 오갈 수 있습니다. $Q$ 일 동안 레이무는 자신의 능력인 순간이동을 연습하기로 했습니다. $i$ 번째 날에는 $A_i$ 번 신사에서 시작해서 마리사가 있는 $B_i$ 번 신사까지 가려고 합니다. 레이무는 다음 동작을 이용해 신사 사이를 이동합니다.

  • 현재 신사와 길로 직접 연결된 다른 신사 중 하나를 선택해서 이동합니다.
  • 지금 있는 신사가 명신대사이면, 지금 있는 신사를 포함한 $K$ 개의 명신대사 중 하나에 동일한 확률로 무작위로 순간이동 합니다.

마리사는 레이무가 빨리 연습을 끝내고 놀아주기를 원하기 때문에 어떤 순서로 동작을 사용해야하는지 알려주려고 합니다. 매 순간 $B_i$ 번 신사까지 도착하기 위해 사용하는 동작 횟수의 기댓값이 최소가 되는 선택을 한다고 할 때, $A_i$번 신사에서 $B_i$번 신사까지 가는 동작 횟수의 기댓값을 출력하세요.

입력

첫 줄에 $N, K, Q$가 공백으로 구분되어 주어집니다. $(2 \le N \le 100\,000; 1 \le K \le N; 1 \le Q \le 500\,000)$

다음 $N-1$ 개의 줄의 $i$ 번째 줄에는 $u_i, v_i$가 주어집니다. 이는 $u_i$번 신사와 $v_i$번 신사가 길로 연결되어있다는 것을 의미합니다. $(1 \le u_i < v_i \le N)$ 임의의 두 신사를 한 개 이상의 길을 사용해 오갈 수 있다는 것이 보장됩니다.

다음 줄에 명신대사의 신사 번호 $p_1, p_2, \cdots, p_K$가 주어집니다. $(1 \le p_1 < p_2 < \cdots < p_K \le N)$

다음 $Q$ 개의 줄의 $i$ 번째 줄에는 $A_i, B_i$가 주어집니다. 이는 $i$ 번째 날에 $A_i$ 번 신사에서 시작해서 $B_i$ 번 신사까지 간다는 의미입니다. $(1 \le A_i, B_i \le N; A_i \neq B_i)$

출력

$Q$ 개의 줄을 출력합니다. $i$번째 줄에는 $A_i$ 번 신사에서 $B_i$ 번 신사로 도착하기 위한 동작 횟수의 기댓값을 출력합니다.

정답과의 상대 오차가 $10^{-9}$ 이하여야 합니다.

예제 입력 1

8 5 2
1 2
2 3
3 4
4 5
4 6
4 7
4 8
1 5 6 7 8
1 4
4 1

예제 출력 1

2.25
3

$1$번 신사에서 $4$번 신사로 갈 때는 순간이동을 사용해서 $5, 6, 7, 8$번 중 하나의 신사로 도착할 때까지 반복한 이후 $4$번 신사로 이동하는 것이 최적입니다.

$4$번 신사에서 $1$번 신사로 갈 때는 순간이동을 사용하지 않고 $4 \rightarrow 3 \rightarrow 2 \rightarrow 1$번 신사 순으로 이동하는 것이 최적입니다.