Lùa mèo
Đề bài
Mô tả
Bạn sắp mở một quán cà phê mèo ở Baku và muốn chụp một bức ảnh quảng cáo có tất cả các chú mèo ngồi ở cửa sổ phía trước. Thật không may, bắt mèo làm theo ý mình là một bài toán khó có tiếng. Nhưng bạn có một kế hoạch: bạn đã mua cây bạc hà mèo, mỗi cây thuộc một giống khác nhau, và biết rằng mỗi chú mèo thích một số giống trong đó. Ở cửa sổ có một hàng gồm chậu, đánh số từ đến theo thứ tự, và bạn sẽ đặt mỗi cây vào đúng một chậu. Sau đó mỗi chú mèo sẽ được dụ (bằng một món đồ chơi buộc dây) đi dọc hàng chậu từ chậu đến chậu . Ngay khi đến một chậu có cây bạc hà mèo mà nó thích, chú mèo sẽ dừng lại ở đó, kể cả khi ở cây đó đã có những chú mèo khác.
Bạn biết bạn muốn mỗi chú mèo dừng lại cạnh chậu nào. Hãy xác định xem có cách đặt các cây vào các chậu để đạt được điều đó hay không.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), là số bộ test. Tiếp theo là mô tả của bộ test.
Dòng đầu tiên của mỗi bộ test chứa hai số nguyên và , trong đó () là số chú mèo và () là số cây bạc hà mèo (cũng là số chậu). Các cây được đánh số từ đến .
Mỗi dòng trong dòng tiếp theo mô tả một chú mèo. Dòng bắt đầu bằng hai số nguyên và , trong đó () là chậu mà chú mèo cần dừng lại và () là số cây mà chú mèo thích. Phần còn lại của dòng gồm số nguyên phân biệt, là số hiệu các cây mà chú mèo thích.
Dữ liệu ra
Với mỗi bộ test, in ra yes nếu có thể sắp xếp các cây như mô tả ở trên, hoặc no nếu không thể.
Ràng buộc
- .
- ; ; .
- Tổng trên mọi bộ test không vượt quá , tổng không vượt quá , tổng mọi không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 5 2 2 1 5 2 3 1 4 5 4 2 3 4 3 5 2 2 1 5 2 3 1 4 5 5 2 3 4 |
yes no |
Ở bộ test thứ nhất, một cách đặt cây hợp lệ là (chậu chứa cây thứ trong dãy). Khi đó mèo 1 dừng ở chậu 2 vì đó là chậu đầu tiên có giống cây nó thích. Mèo 2 cũng dừng ở đó. Mèo 3 đi tiếp đến tận chậu 4. Ở bộ test thứ hai, mèo 3 phải dừng ở chậu 5, nên cả cây 3 và cây 4 đều không được đặt trước chậu 5, nhưng chỉ có một chậu như vậy. |
| 1 2 3 1 1 2 3 2 1 2 |
no | Mèo 1 chỉ thích cây 2 nên cây 2 phải ở chậu 1. Nhưng mèo 2 cũng thích cây 2, nên nó sẽ dừng ở chậu 1 chứ không phải chậu 3. |
Bình luận