Nhà tù IOI nổi tiếng là nhà tù được quản lý nghiêm ngặt nhất vương quốc JOI. Nhà tù có \(N\) phòng, được đánh số từ \(1\) đến \(N\), và \(N-1\) hành lang. Hành lang thứ \(i\) (\(1\le i\le N-1\)) nối hai chiều phòng \(A_i\) với phòng \(B_i\). Từ một phòng bất kỳ có thể đi đến mọi phòng khác qua các hành lang.

Có \(M\) tù nhân, được đánh số từ \(1\) đến \(M\). Tù nhân \(j\) (\(1\le j\le M\)) có phòng ngủ là \(S_j\) và phòng làm việc là \(T_j\). Phòng ngủ của một người có thể là phòng làm việc của người khác. Tuy nhiên, không có hai người chung phòng ngủ, cũng không có hai người chung phòng làm việc.

Một buổi sáng, tất cả tù nhân phải đi từ phòng ngủ đến phòng làm việc. Giám đốc APIO sẽ lặp lại mệnh lệnh sau:

• Chọn một tù nhân và chuyển người đó từ phòng hiện tại sang một phòng được nối trực tiếp bằng một hành lang. Để tránh các tù nhân nói chuyện với nhau, phòng đích không được có tù nhân khác.

Để công việc bắt đầu sớm, giám đốc muốn biết có thể đưa tất cả tù nhân đến phòng làm việc mà không ai đi qua cùng một phòng hai lần hay không. Nói cách khác, mỗi tù nhân phải đi theo đường đi ngắn nhất của mình.

Hãy viết chương trình xác định điều đó từ thông tin các phòng, hành lang và tù nhân.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Mỗi bộ dữ liệu gồm \(Q\) tình huống, được đánh số từ \(1\) đến \(Q\):

Q
(Dữ liệu tình huống 1)
(Dữ liệu tình huống 2)
...
(Dữ liệu tình huống Q)

Mỗi tình huống có định dạng sau; tất cả giá trị đều là số nguyên:

N
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}
M
S_1 T_1
S_2 T_2
...
S_M T_M

Dữ liệu ra

In \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(k\) (\(1\le k\le Q\)) chứa Yes nếu có thể đưa tất cả tù nhân trong tình huống \(k\) đến phòng làm việc theo các đường đi ngắn nhất, hoặc No nếu không thể.

Ràng buộc

• \(1\le Q\le 1\,000\).
• \(2\le N\le 120\,000\).
• \(1\le A_i<B_i\le N\) (\(1\le i\le N-1\)).
• \(2\le M\le N\).
• \(1\le S_j,T_j\le N\) và \(S_j\ne T_j\) (\(1\le j\le M\)).
• Các giá trị \(S_1,S_2,\ldots,S_M\) đôi một khác nhau.
• Các giá trị \(T_1,T_2,\ldots,T_M\) đôi một khác nhau.
• Từ bất kỳ phòng nào đều đi được đến mọi phòng khác qua các hành lang.
• Tổng \(N\) của cả \(Q\) tình huống không vượt quá \(120\,000\).

Phân nhóm

Các ràng buộc về một tình huống dưới đây phải đúng với mọi tình huống trong bộ dữ liệu.

• Nhóm 1 (5 điểm): \(A_i=i\), \(B_i=i+1\) với mọi \(1\le i\le N-1\).
• Nhóm 2 (5 điểm): \(Q\le 20\), \(N\le 250\), \(M=2\).
• Nhóm 3 (16 điểm): \(Q\le 20\), \(N\le 250\), \(M\le 6\).
• Nhóm 4 (28 điểm): \(Q\le 20\), \(N\le 250\), \(M\le 100\).
• Nhóm 5 (12 điểm): \(Q\le 20\), \(M\le 500\).
• Nhóm 6 (11 điểm): Từ bất kỳ phòng nào đều có thể đến mọi phòng khác qua không quá \(20\) hành lang.
• Nhóm 7 (23 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

Yes

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

Yes
No

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

Yes
No
Yes

Nguồn

Bài toán thuộc JOI 2021/2022, trại huấn luyện mùa xuân, ngày thi 1 (20/03/2022). Bản gốc do JCIOI phát hành theo giấy phép CC BY-SA 4.0. Bản tiếng Việt là bản dịch từ đề chính thức.