3. USACO 2022 - Bracelet Crossings
Bessie thích làm đồ thủ công mỹ nghệ. Trong thời gian rảnh, cô đã làm \(N\) chiếc vòng tay (\(1\le N\le 50\)), được đánh số thuận tiện từ \(1 \ldots N\). Vòng tay thứ \(i\) được sơn màu \(i\) trong một tập gồm \(N\) màu khác nhau. Sau khi làm xong, Bessie đặt chúng lên bàn để trưng bày (có thể xem mặt bàn là mặt phẳng hai chiều). Cô cẩn thận sắp xếp các vòng tay sao cho thỏa mãn ba điều kiện sau:
- Mỗi vòng tay là một chuỗi đa giác khép kín duy nhất — một dãy các đỉnh (điểm) được nối tuần tự bằng các đoạn thẳng, trong đó điểm đầu và điểm cuối trùng nhau (bạn có thể tham khảo trang Wikipedia về chuỗi đa giác để biết thêm chi tiết);
- Không vòng tay nào tự cắt chính nó (tương ứng với một chuỗi đa giác "đơn"); và
- Không có hai vòng tay nào cắt nhau.
Không may, ngay sau khi Bessie sắp xếp các vòng tay cẩn thận như vậy, Farmer John lái máy kéo đi ngang qua, làm rung chiếc bàn và khiến các vòng tay xê dịch, đồng thời có thể đứt thành nhiều chuỗi đa giác (không nhất thiết khép kín hoặc đơn)! Sau đó, Bessie muốn kiểm tra xem ba điều kiện trên còn được thỏa mãn hay không. Tuy nhiên, lúc ấy trời tối nên cô không thể nhìn thấy các vòng tay nữa.
May thay, Bessie có một chiếc đèn pin. Cô chọn \(M\) đường thẳng đứng (\(1\le M\le 50\)) là \(x=1,x=2,\ldots,x=M\) và, với mỗi đường, cô quét chùm sáng đèn pin dọc theo đường đó từ \(y=-\infty\) đến \(y=\infty\), ghi lại màu của tất cả các vòng tay nhìn thấy theo thứ tự chúng xuất hiện. May mắn là không chùm sáng nào đi qua một đỉnh của bất kỳ chuỗi đa giác nào hoặc đi qua hai đoạn thẳng cùng một lúc. Hơn nữa, với mỗi chùm sáng, mỗi màu xuất hiện đều xuất hiện đúng hai lần.
Bạn có thể giúp Bessie dùng thông tin này để xác định liệu các vòng tay vẫn có thể thỏa mãn cả ba điều kiện trên hay không?
Dữ liệu vào
Mỗi dữ liệu vào chứa \(T\) bộ dữ liệu con (\(1 \leq T \leq 50\)), tất cả phải được giải độc lập và chính xác để giải được toàn bộ dữ liệu. Các bộ dữ liệu con liên tiếp được ngăn cách bằng dòng trống.
Dòng đầu tiên chứa \(T\). Sau đó là \(T\) bộ dữ liệu con.
Dòng đầu tiên của mỗi bộ dữ liệu con chứa hai số nguyên \(N\) và \(M\). Tiếp theo là \(M\) dòng. Với mỗi \(i\) từ \(1\) đến \(M\), dòng thứ \(i\) trong số các dòng bổ sung chứa một số nguyên \(k_i\) (\(0\le k_i\le 2N\), \(k_i\) chẵn), theo sau là \(k_i\) số nguyên \(c_{i1},c_{i2},\ldots,c_{ik_i}\) (\(c_{ij}\in[1,N]\), mỗi \(c_{ij}\) xuất hiện không lần nào hoặc hai lần). Điều này có nghĩa là khi Bessie quét đèn pin từ \((i,-\infty)\) đến \((i,\infty)\), cô lần lượt bắt gặp các màu \(c_{i1},c_{i2},\ldots,c_{ik_i}\).
Dữ liệu ra
Với mỗi bộ dữ liệu con, in YES nếu cả ba điều kiện trên có thể được thỏa mãn. Nếu không, in NO.
Phân nhóm
- Dữ liệu 2: \(N=1\).
- Dữ liệu 3–5: \(N=2\).
- Dữ liệu 6–8: \(M=1\).
- Dữ liệu 9–14: \(M=2\).
- Dữ liệu 15–20: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
5
1 2
2 1 1
2 1 1
1 3
2 1 1
0
2 1 1
2 1
4 1 2 1 2
4 2
6 1 2 2 3 3 1
6 1 2 4 4 2 1
2 2
4 1 1 2 2
4 2 2 1 1Output
YES
NO
NO
YES
NOGiải thích
Một cấu hình vòng tay khả thi cho bộ dữ liệu con thứ nhất là:
Với bộ dữ liệu con thứ tư, một cách sắp xếp khả thi là:
Nguồn
USACO 2021 December Contest, Gold — Bracelet Crossings. Tác giả: Richard Qi.