| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 112 | 37 | 33 | 33.333% |
JOI Kingdom is an insular country consisting of $N$ islands, numbered from 1ドル$ to $N$. The islands are connected by $N - 1$ bridges, numbered from 1ドル$ to $N - 1$. The bridge $i$ (1ドル ≤ i ≤ N - 1$) connects the island $A_i$ and the island $B_i$ bidirectionally. It is possible to travel from any island to any other island by passing through a number of bridges.
In JOI Kingdom, there are $M$ sightseeing spots, numbered from 1ドル$ to $M$. The sightseeing spot $j$ (1ドル ≤ j ≤ M$) is located in the island $C_j$.
There are $Q$ travelers. They plan to visit sightseeing spots in JOI Kingdom. The travelers are numbered from 1ドル$ to $Q$. Each traveler makes a trip in the following way.
The traveler $k$ (1ドル ≤ k ≤ Q$) wants to visit all of the sightseeing spots $L_k, L_{k + 1}, \dots , R_k$. However, since the budget is limited, the traveler $k$ wants to minimize the number of islands where the traveler $k$ visits at least once.
Write a program which, given information of JOI Kingdom and the travelers, calculates, for each $k$ (1ドル ≤ k ≤ Q$), the minimum possible number of islands where the traveler $k$ visits at least once.
Read the following data from the standard input.
$N$ $M$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$
$C_1$ $C_2$ $\cdots$ $C_M$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$
Write $Q$ lines to the standard output. The $k$-th line (1ドル ≤ k ≤ Q$) of output should contain the minimum possible number of islands where the traveler $k$ visits at least once.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N ≤ 300,ドル $M ≤ 300,ドル $Q ≤ 300$. |
| 2 | 5 | $N ≤ 2,000円,ドル $M ≤ 2,000円,ドル $Q ≤ 2,000円$. |
| 3 | 7 | $A_i = i,ドル $B_i = i + 1$ (1ドル ≤ i ≤ N - 1$). |
| 4 | 18 | $L_1 = 1,ドル $R_k + 1 = L_{k+1}$ (1ドル ≤ k ≤ Q - 1$), $R_Q = M$. |
| 5 | 24 | $A_i = \left\lfloor \frac{i+1}{2} \right\rfloor,ドル $B_i = i + 1$ (1ドル ≤ i ≤ N - 1$). Here, $\left\lfloor x \right\rfloor$ is the largest integer not exceeding $x$. |
| 6 | 41 | No additional constraints. |
7 6 2 1 2 1 3 2 4 2 5 3 6 3 7 2 3 6 4 5 7 1 3 4 6
4 6
The traveler 1ドル$ makes a trip in the following way, and visits all of the sightseeing spots 1,ドル 2, 3$.
The islands 1,ドル 2, 3, 6$ are the four islands where the traveler 1ドル$ visits at least once. If the number of islands traveler 1ドル$ visits at least once is less than or equal to 3ドル,ドル it is impossible to visit all of the sightseeing spots 1,ドル 2, 3$. Therefore, output 4ドル$ in the first line.
The traveler 2ドル$ makes a trip in the following way, and visits all of the sightseeing spots 4,ドル 5, 6$.
The islands 1,ドル 2, 3, 4, 5, 7$ are the six islands where the traveler 2ドル$ visits at least once. If the number of islands traveler 2ドル$ visits at least once is less than or equal to 5ドル,ドル it is impossible to visit all of the sightseeing spots 4,ドル 5, 6$. Therefore, output 6ドル$ in the second line.
This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6.
8 8 9 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 6 4 3 5 2 4 7 3 5 4 6 6 8 1 4 2 3 6 8 5 5 2 8 1 2
3 4 6 6 3 6 1 6 3
This sample input satisfies the constraints of Subtasks 1, 2, 3, 6.
10 7 9 6 5 3 6 9 3 8 3 7 8 7 1 2 5 7 10 8 4 9 4 10 1 10 7 6 4 4 1 3 1 3 6 7 3 6 3 3 1 5 2 5 1 2
1 6 6 4 3 1 7 5 4
This sample input satisfies the constraints of Subtasks 1, 2, 6.