Bạn là một kiếm sĩ quyết đấu, khao khát trở thành Kiếm Sư tiếp theo. Để đạt danh hiệu này, bạn sẽ đấu với các đối thủ cho đến khi thắng tất cả họ. Mọi đối thủ luôn sẵn sàng quyết đấu và họ không đấu với nhau.

Mỗi kiếm sĩ, kể cả bạn, biết ít nhất một đòn tấn công và một thế phòng thủ. Trên thế giới có tối đa \(P\) cặp tấn công–phòng thủ; thế thủ thứ \(i\) chỉ hóa giải đòn công thứ \(i\), và đòn công thứ \(i\) cũng chỉ bị thế thủ thứ \(i\) hóa giải. Có thể tồn tại đòn công hoặc thế thủ không ai biết. Một kỹ năng đã biết có thể dùng bao nhiêu lần tùy ý, không bị “tiêu hao”.

Mỗi trận quyết đấu tuân theo các quy tắc:

• Là ứng viên Kiếm Sư, bạn luôn tấn công trước. Bạn chọn một đòn công mình biết. Nếu đối thủ biết thế thủ tương ứng, họ có thể chọn dùng nó; nếu không biết hoặc chọn không dùng, họ không phòng thủ.
• Sau đó đối thủ chọn một đòn công họ biết. Nếu bạn biết thế thủ tương ứng, bạn có thể chọn dùng; nếu không biết hoặc chọn không dùng, bạn không phòng thủ.
• Nếu bạn phòng thủ thành công còn đối thủ không phòng thủ, bạn thắng trận. Trong mọi trường hợp khác bạn không thắng, nhưng hành trình trở thành Kiếm Sư vẫn có thể tiếp tục.

Bạn có thể đấu bao nhiêu trận tùy ý, kể cả đấu nhiều lần với cùng một người, bất kể kết quả trước đó. Không cần lập sẵn toàn bộ lịch; quyết định tiếp theo có thể dựa trên những gì đã xảy ra. Khi đã thắng mỗi đối thủ ít nhất một lần, bạn trở thành Kiếm Sư.

Bạn học cực nhanh. Sau mỗi trận, bất kể kết quả, bạn thêm vào bộ kỹ năng của mình đòn công và thế thủ, nếu có, mà đối thủ đã dùng. Nếu đối thủ dùng một thế thủ lạ chống lại bạn, bạn chỉ học nó sau trận, nên không thể dùng nó để chống đòn công của đối thủ ngay trong cùng trận. Chỉ bạn có lợi thế học hỏi này; kỹ năng của đối thủ không bao giờ thay đổi.

Hơn nữa, sau khi bạn thắng một đối thủ và trước trận tiếp theo, người đó sẽ dạy bạn toàn bộ đòn công và thế thủ họ biết mà bạn chưa biết. Một khi đã thua bạn, họ sẽ trông đỡ tệ hơn nếu cuối cùng bạn thật sự trở thành Kiếm Sư.

Bạn biết trước mọi đòn công và thế thủ của từng đối thủ. Nếu lựa chọn tối ưu, liệu bạn có thể bảo đảm trở thành Kiếm Sư, bất kể các đối thủ lựa chọn thế nào hay không?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test có cấu trúc:

• Dòng đầu chứa \(N,P\): số kiếm sĩ, kể cả bạn, và số cặp tấn công–phòng thủ tối đa.
• Tiếp theo là \(N\) nhóm, mỗi nhóm ba dòng, mô tả một kiếm sĩ; nhóm đầu tiên mô tả bạn:
  1. Một dòng chứa \(Attacks_i,Defenses_i\), số đòn công và số thế thủ kiếm sĩ \(i\) biết.
  2. Một dòng chứa \(Attacks_i\) số nguyên phân biệt \(A_{ij}\) theo thứ tự tăng dần, là chỉ số các đòn công họ biết.
  3. Một dòng chứa \(Defenses_i\) số nguyên phân biệt \(D_{ij}\) theo thứ tự tăng dần, là chỉ số các thế thủ họ biết.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\), và y là YES nếu có thể bảo đảm trở thành Kiếm Sư, hoặc NO nếu không.

Ràng buộc

• \(1\le T\le100\).
• \(2\le N\le1000\).
• \(1\le P\le1000\).
• \(1\le Attacks_i,Defenses_i\le P\) với mọi \(i\).
• \(1\le A_{ij}<A_{i,j+1}\le P\) với mọi chỉ số hợp lệ.
• \(1\le D_{ij}<D_{i,j+1}\le P\) với mọi chỉ số hợp lệ.
• Tổng mọi \(Attacks_i\) cộng tổng mọi \(Defenses_i\) không vượt \(50000\).

Phân nhóm

Test Set 1 (Visible): \(A_{i1}=1\) và \(D_{i1}=1\) với mọi \(i\); mọi kiếm sĩ, kể cả bạn, đều biết đòn công \(1\) và thế thủ \(1\).

Test Set 2 (Hidden): Không có ràng buộc bổ sung.

Đ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ụ

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

Case #1: NO
Case #2: YES
Case #3: NO
Case #4: NO
Case #5: YES

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài Swordmaster.

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