Bạn có hình ảnh của hai tác phẩm điêu khắc. Các tác phẩm điêu khắc bao gồm nhiều quả cầu kim loại đặc và một số ống cao su nối các cặp quả cầu. Các ống trong mỗi tác phẩm được kết nối theo cách mà đối với bất kỳ cặp quả cầu nào, đều có đúng một đường đi men theo một chuỗi các ống (không lặp lại bất kỳ ống nào) giữa hai quả cầu đó. Tất cả các quả cầu đều có cùng bán kính và tất cả các ống đều có cùng chiều dài.

Bạn nghi ngờ rằng tác phẩm điêu khắc nhỏ hơn trong số hai tác phẩm thực chất được tạo ra bằng cách đơn giản là loại bỏ một số quả cầu và ống từ tác phẩm lớn hơn. Bạn muốn viết một chương trình để kiểm tra xem điều này có khả thi hay không.

Dữ liệu vào sẽ chứa một số bộ test. Một tác phẩm điêu khắc được mô tả bằng cách đánh số các quả cầu liên tiếp từ 1 và liệt kê các cặp quả cầu được nối với nhau bằng ống. Việc đánh số được chọn độc lập cho mỗi tác phẩm điêu khắc.

Dữ liệu vào

• Một dòng chứa một số nguyên C, số lượng bộ test trong file dữ liệu.

Đối với mỗi bộ test:

• Một dòng chứa số nguyên N, số lượng quả cầu trong tác phẩm điêu khắc lớn.
• N−1 dòng, mỗi dòng chứa một cặp số nguyên cách nhau bởi dấu cách, cho biết hai quả cầu có số hiệu đó trong tác phẩm điêu khắc lớn được nối với nhau bằng một ống.
• Một dòng chứa số nguyên M, số lượng quả cầu trong tác phẩm điêu khắc nhỏ.
• M−1 dòng, mỗi dòng chứa một cặp số nguyên cách nhau bởi dấu cách, cho biết hai quả cầu có số hiệu đó trong tác phẩm điêu khắc nhỏ được nối với nhau bằng một ống.

Dữ liệu ra

• C dòng, mỗi dòng cho một bộ test theo thứ tự xuất hiện trong file dữ liệu, chứa "Case #X: YES" nếu tác phẩm điêu khắc nhỏ trong trường hợp X có thể được tạo ra từ tác phẩm điêu khắc lớn trong trường hợp X, hoặc "Case #X: NO" nếu không thể. (X là số thứ tự của bộ test, từ 1 đến C.)

Ràng buộc

Phân nhóm

• Small dataset (Test set 1 - Visible):
  • 1 ≤ C ≤ 100
  • 2 ≤ N ≤ 8
  • 1 ≤ M < N
• Large dataset (Test set 2 - Hidden):
  • 1 ≤ C ≤ 50
  • 2 ≤ N ≤ 100
  • 1 ≤ M < N

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
5
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
5
1 2
1 3
1 4
4 5
4
1 2
2 3
3 4

Case #1: NO
Case #2: YES

Nguồn

Google Code Jam 2008, Vòng bán kết châu Á - Thái Bình Dương, bài Modern Art Plagiarism.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.