trang chủ / đề bài / icpcwf25_f

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 m 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 m chậu, đánh số từ 1 đến m 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 1 đến chậu m. 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 t (1≤t≤10000), là số bộ test. Tiếp theo là mô tả của t bộ test.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên n và m, trong đó n (1≤n≤2·105) là số chú mèo và m (1≤m≤2·105) là số cây bạc hà mèo (cũng là số chậu). Các cây được đánh số từ 1 đến m.

Mỗi dòng trong n dòng tiếp theo mô tả một chú mèo. Dòng bắt đầu bằng hai số nguyên p và k, trong đó p (1≤p≤m) là chậu mà chú mèo cần dừng lại và k (1≤k≤m) là số cây mà chú mèo thích. Phần còn lại của dòng gồm k 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

  • 1≤t≤10000.
  • 1≤n,m≤2·105; 1≤p≤m; 1≤k≤m.
  • Tổng n trên mọi bộ test không vượt quá 2·105, tổng m không vượt quá 2·105, tổng mọi k không vượt quá 5·105.

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à [2,1,5,3,4] (chậu i chứa cây thứ i 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0