Vương quốc JOI gồm \(N\) hòn đảo, đánh số từ \(1\) đến \(N\). Có \(N-1\) cây cầu, đánh số từ \(1\) đến \(N-1\). Cầu \(i\) nối hai đảo \(A_i\) và \(B_i\) theo cả hai chiều. Từ bất kỳ đảo nào cũng có thể đi đến bất kỳ đảo khác bằng cách qua một số cây cầu.

Vương quốc có \(M\) địa điểm tham quan, đánh số từ \(1\) đến \(M\). Địa điểm \(j\) nằm trên đảo \(C_j\).

Có \(Q\) du khách, đánh số từ \(1\) đến \(Q\), dự định đến tham quan. Mỗi người thực hiện chuyến đi như sau:

1. Chọn một đảo \(x\) với \(1\le x\le N\) và đáp máy bay xuống đảo đó.
2. Thực hiện nhiều lần các hành động sau, với loại hành động và thứ tự tùy ý: chọn một địa điểm tham quan trên đảo hiện tại để ghé thăm; hoặc đi qua một cây cầu đến đảo khác.
3. Từ đảo hiện tại, đáp máy bay rời vương quốc.

Du khách \(k\) muốn ghé thăm tất cả các địa điểm \(L_k,L_k+1,\ldots,R_k\). Vì ngân sách có hạn, người đó muốn giảm thiểu số đảo khác nhau đã đặt chân đến ít nhất một lần, kể cả các đảo chỉ đi qua.

Cho thông tin vương quốc và yêu cầu của các du khách, hãy tìm số đảo nhỏ nhất có thể cho từng người.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N M Q
A_1 B_1
A_2 B_2
...
A_(N-1) B_(N-1)
C_1 C_2 ... C_M
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dữ liệu ra

In \(Q\) dòng. Dòng \(k\) chứa số đảo khác nhau ít nhất mà du khách \(k\) cần đặt chân đến để ghé thăm mọi địa điểm yêu cầu.

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le M\le 100\,000\).
• \(1\le Q\le 100\,000\).
• \(1\le A_i,B_i\le N\) với \(1\le i<N\).
• Từ bất kỳ đảo nào cũng có thể đi đến bất kỳ đảo khác qua các cây cầu.
• \(1\le C_j\le N\) với \(1\le j\le M\).
• \(1\le L_k\le R_k\le M\) với \(1\le k\le Q\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (5 điểm): \(N\le 300\), \(M\le 300\), \(Q\le 300\).
• Nhóm 2 (5 điểm): \(N\le 2000\), \(M\le 2000\), \(Q\le 2000\).
• Nhóm 3 (7 điểm): \(A_i=i\), \(B_i=i+1\) với mọi \(1\le i<N\).
• Nhóm 4 (18 điểm): \(L_1=1\), \(R_k+1=L_{k+1}\) với mọi \(1\le k<Q\), và \(R_Q=M\).
• Nhóm 5 (24 điểm): \(A_i=\lfloor(i+1)/2\rfloor\), \(B_i=i+1\) với mọi \(1\le i<N\). Ký hiệu \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).
• Nhóm 6 (41 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

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

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

Nguồn

JOI 2022/2023 Spring Training, Contest 3, 21/03/2023. Đề gốc của JCIOI; bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.